En teoría de grafos, el Grafo de McGee o jaula-(3-7) es un 3-grafo regular de 24 vértices y 36 aristas.
Es la única (3,7)-jaula (el menor grafo cúbico de girth 7). Es también la menor jaula cúbica que no es un grafo de Moore.
Descubierto por primera vez por Sachs pero no publicado por éste,Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960 el grafo debe su nombre a McGee, quien publicó el resultado en 1960.McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960 Luego Tutte en 1966 demostró que este grafo correspondía a la única jaula-(3,7).Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
Actualmente se conocen los menores grafos cúbicos con números de cruzamiento 1–8 . El menor grafo con cruzamiento 8 es el grafo de McGee. Existen 5 grafos cúbicos no isomórficos de orden 24 con número de cruzamiento 8.Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009 Uno de ellos es el grafo de Petersen generalizado G(12,5), también conocido como el grafo de Nauru.
El grafo de McGee tiene radio 4, diámetro 4, número cromático 3 e índice cromático 3.
Propiedades algebraicas El polinomio característico del grafo de McGee es: .
Galería
Referencias
McGee