Conde mcgee
| conde mcgee | |
|---|---|
| Lleva el nombre de | WF McGee |
| picos | 24 |
| costillas | 36 |
| Radio | cuatro |
| Diámetro | cuatro |
| Circunferencia | 7 |
| automorfismos | 32 |
| Número cromático | 3 |
| índice cromático | 3 |
| Propiedades |
celda cúbica hamiltoniana |
| Archivos multimedia en Wikimedia Commons | |
En teoría de grafos, un gráfico de McGee , o (3-7) celdas , es un gráfico regular de 3 con 24 vértices y 36 aristas. [una]
Graph McGee es la única celda (3,7) (cúbica más pequeña con circunferencia 7). Es la celda cúbica de gráfico no Moore más pequeña .
Primero descubierto por Horst Sachs, pero no publicado [2] , el gráfico lleva el nombre de McGee ( WF McGee ), quien publicó el resultado en 1960 [3] . Más tarde, en 1966 , William Thomas Tutt demostró que esta es la única celda (3,7) [4] [5] [6] .
Se conocen los gráficos cúbicos más pequeños con 1 a 8 cruces (secuencia A110507 en OEIS ), el gráfico más pequeño con 8 cruces es el gráfico de McGee. Hay 5 grafos cúbicos no isomorfos de orden 24 con 8 cruces [7] , uno de ellos es el grafo de Petersen generalizado G (12,5), también conocido como el grafo de Nauru [8] .
El gráfico 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 está conectado por 3 vértices y por 3 bordes .
Propiedades algebraicas
El polinomio característico del gráfico de McGee es .
El automorfismo del grupo de gráficos de McGee tiene un orden de 32 y no es transitivo de vértice: hay dos órbitas de vértice de longitud 8 y 16. El gráfico de McGee es la celda cúbica más pequeña que no es transitiva de vértice [9] .
Galería
-
El número de intersecciones del gráfico de McGee es 8.
-
El número cromático del Conde McGee es 3.
-
El índice cromático de Count McGee es 3.
-
El índice cromático acíclico del gráfico de McGee es 3.
-
Representación alternativa del conde McGee.
Notas
- ↑ Weisstein, Eric W. McGee Graph en el sitio web de Wolfram 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 "Un gráfico cúbico mínimo de circunferencia siete". Canadá. Matemáticas. Toro. 3, 149-152, 1960
- ↑ Tutte, WT Conectividad en gráficos. Toronto, Ontario: Prensa de la Universidad de Toronto, 1966
- ↑ Wong, PK "Jaulas: una encuesta". J Gráfico Th. 6, 1-22, 1982
- ↑ Brouwer, AE; Cohen, AM; y Neumaier, A. Distancia de gráficos regulares. Nueva York: Springer-Verlag, pág. 209, 1989
- ↑ Pegg, E.T. y Exoo, G. "Crossing Number Graphs". Matemática J. 11, 2009
- ↑ Weisstein, Eric W. Graph Crossing Number en el sitio web de Wolfram MathWorld .
- ↑ Bondy, JA y Murty, USR Graph Theory with Applications. Nueva York: Holanda Septentrional, pág. 237, 1976.