The McGee Graph
|Named after||W. F. McGee|
The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in OEIS). The smallest 8-crossing graph is the McGee graph. There exists 5 non-isomorphic cubic graphs of order 24 with crossing number 8. One of them is the generalized Petersen graph G(12,5), also known as the Nauru graph.
The characteristic polynomial of the McGeeGraph graph is : .
The automorphism group of the McGee graph is of order 32 and doesn't acts transitively upon its vertices: there are two vertex orbits of lengths 8 and 16. The McGee is the smallest cubic cage that is not a vertex-transitive graph.
The crossing number of the McGee graph is 8.
The chromatic number of the McGee graph is 3.
The chromatic index of the McGee graph is 3.
The acyclic chromatic number of the McGee graph is 3.
- Weisstein, Eric W., "McGee Graph", MathWorld.
- Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
- McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960
- Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
- Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982
- Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
- Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- Weisstein, Eric W., "Graph Crossing Number", MathWorld.
- Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.