Tutte 12 jaulas
| Tutte 12 jaulas | |
|---|---|
 El Tutte de 12 jaulas | |
| Lleva el nombre de | WT Tutte |
| Vértices | 126 |
| Bordes | 189 |
| Radio | 6 |
| Diámetro | 6 |
| Circunferencia | 12 |
| Automorfismos | 12096 |
| Número cromático | 2 |
| Índice cromático | 3 |
| Propiedades | Jaula cúbica Hamiltoniana Semi-simétrica Bipartita |
| Tabla de gráficos y parámetros | |
En el campo matemático de la teoría de grafos , el grafo de Tutte de 12 jaulas o de Benson [1] es un grafo 3- regular con 126 vértices y 189 aristas que llevan el nombre de WT Tutte . [2]
El Tutte 12-jaula es el único (3-12) - jaula (secuencia A052453 en la OEIS ). Fue descubierto por CT Benson en 1966. [3] Tiene número cromático 2 ( bipartito ), índice cromático 3, circunferencia 12 (como una jaula de 12) y diámetro 6. Su número de cruce es 170 y se ha conjeturado que es el gráfico cúbico más pequeño con este número de cruce. [4] [5]
Construcción
El Tutte 12-cage es un gráfico hamiltoniano cúbico y se puede definir mediante la notación LCF [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57 , 11, –21, –57, 59, –17] 7 . [6]
Hay, hasta el isomorfismo, precisamente dos hexágonos generalizados de orden (2,2) como lo demuestran Cohen y Tits. Son el hexágono Cayley dividido H (2) y su línea de puntos dual. Claramente, ambos tienen el mismo gráfico de incidencia, que de hecho es isomorfo al Tutte de 12 jaulas. [1]
La jaula Balaban 11 se puede construir por escisión de la jaula Tutte 12 eliminando un pequeño subárbol y suprimiendo los vértices resultantes de grado dos. [7]
Propiedades algebraicas
El grupo automorphism de la Tutte 12 de jaula es del orden de 12.096 y es un producto semi-directo de la proyectiva especial unitaria grupo PSU (3,3) con el grupo cíclico Z / 2 Z . [1] Actúa de forma transitiva en sus bordes pero no en sus vértices, lo que lo convierte en un gráfico semi-simétrico , un gráfico regular que es transitivo por bordes pero no transitivo por vértices . De hecho, el grupo de automorfismo del Tutte 12-cage conserva las partes bipartitas y actúa primitivamente en cada parte. Estos gráficos se denominan gráficos bi-primitivos y sólo existen cinco gráficos bi-primitivos cúbicos; se denominan gráficas de Iofinova-Ivanov y son del orden 110, 126, 182, 506 y 990.[8]
Se conocen todas las gráficas cúbicas semi-simétricas de hasta 768 vértices. Según Conder , Malnič, Marušič y Potočnik, el Tutte 12-cage es el único gráfico cúbico semi-simétrico en 126 vértices y es el quinto gráfico cúbico semi-simétrico más pequeño posible después del gráfico Gray , el gráfico Iofinova-Ivanov en 110 vértices , el gráfico de Ljubljana y un gráfico de 120 vértices con circunferencia 8. [9]
El polinomio característico del Tutte 12-cage es
Es el único gráfico con este polinomio característico; por lo tanto, la jaula de 12 está determinada por su espectro .
Galería
El número cromático del Tutte 12-cage es 2.
El índice cromático del Tutte 12-cage es 3.
Referencias
- ^ a b c Geoffrey Exoo y Robert Jajcay, Encuesta dinámica de jaulas, Electr. J. Combin. 15 (2008).
- ^ Weisstein, Eric W. "Tutte 12-jaula" . MathWorld .
- ^ Benson, CT "Gráficos mínimos regulares de circunferencia 8 y 12." Poder. J. Math. 18, 1091-1094, 1966.
- ^ Exoo, G. "Dibujos rectilíneos de gráficos famosos" .
- ^ Pegg, ET y Exoo, G. "Crossing Number Graphs". Mathematica J. 11, 2009.
- ^ Polster, B. Un libro de imágenes geométricas. Nueva York: Springer, pág. 179, 1998.
- ^ Balaban, AT "Gráficos trivalentes de circunferencia nueve y once y relaciones entre las jaulas". Rev. Roumaine Math 18, 1033-1043, 1973.
- ^ Iofinova, ME e Ivanov, AA "Gráficos cúbicos bi-primitivos". En Investigaciones en la Teoría Algebraica de Objetos Combinatorios. pp. 123-134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscú, pp. 137-152, 1985.)
- ^ Conder, Marston ; Malnič, Aleksander; Marušič, Dragan ; Potočnik, Primož (2006), "Un censo de gráficos cúbicos semisimétricos de hasta 768 vértices", Journal of Algebraic Combinatorics , 23 : 255-294, doi : 10.1007 / s10801-006-7397-3.
- Gráficos individuales
- Gráficos regulares
