Gráfico con 24 vértices y 36 aristas
En el campo matemático de la teoría de grafos , el grafo de McGee o la jaula (3-7) es un grafo 3-regular con 24 vértices y 36 aristas. [1]
El gráfico de McGee es la única jaula (3,7) (el gráfico cúbico más pequeño de circunferencia 7). También es la jaula cúbica más pequeña que no es un gráfico de Moore .
Descubierto por primera vez por Sachs pero no publicado, [2] el gráfico recibe su nombre de McGee, quien publicó el resultado en 1960. [3] Luego, Tutte demostró que el gráfico de McGee era la única jaula (3,7) en 1966. [4] [5] [6]
El grafo de McGee requiere al menos ocho cruces en cualquier dibujo del mismo en el plano. Es uno de los tres grafos no isomorfos empatados por ser el grafo cúbico más pequeño que requiere ocho cruces. Otro de estos tres grafos es el grafo generalizado de Petersen G (12,5) , también conocido como grafo de Nauru . [7] [8]
El grafo de McGee tiene un radio de 4, un diámetro de 4, un número cromático de 3 y un índice cromático de 3. También es un grafo conexo por 3 vértices y conexo por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. [9]
Propiedades algebraicas
El polinomio característico del gráfico de McGee es
.
El grupo de automorfismos del grafo de McGee es de orden 32 y no actúa transitivamente sobre sus vértices: hay dos órbitas de vértices, de longitudes 8 y 16. El grafo de McGee es la jaula cúbica más pequeña que no es un grafo transitivo de vértices . [10]
Galería
Referencias
- ^ abcdef Weisstein, Eric W. "Gráfico de McGee". MathWorld .
- ^ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo". Cápsula. Naciones Unidas. Estera. Italiano. 15, 522-528, 1960
- ^ McGee, WF (1960). "Un gráfico cúbico mínimo de circunferencia siete". Boletín Matemático Canadiense . 3 (2): 149–152. doi : 10.4153/CMB-1960-018-1 .
- ^ Tutte, WT Conectividad en gráficos. Toronto, Ontario: University of Toronto Press, 1966
- ^ Wong, Pak-Ken (1982). "Jaulas: un estudio". Revista de teoría de grafos . 6 : 1–22. doi :10.1002/jgt.3190060103.
- ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, pág. 209, 1989
- ^ Sloane, N. J. A. (ed.). "Secuencia A110507 (Número de nodos en el grafo cúbico más pequeño con número de cruces n)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
- ^ Pegg, ET ; Exoo, G. (2009). "Gráficos de números cruzados". Mathematica Journal . 11 (2). doi : 10.3888/tmj.11.2-2 ..
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
- ^ Jajcay, Robert; Širáň, Jozef (2011). "Pequeños grafos transitivos de vértice de grado y circunferencia dados". Ars Mathematica Contemporanea . 4 (2): 375–384. doi :10.26493/1855-3974.124.06d.
