TOPICS
Search

McGee Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
McGeeGraphConstruction

The McGee graph is a cubic symmetric graph on 24 nodes and 36 edges which is the unique 7-cage graph. It can be constructed as the union of the two leftmost subgraphs illustrated above (Harary 1994, p. 174). It was discovered by H. Sachs (unpublished; see Kárteszi 1960) and McGee (1960), and proven unique by Tutte (1966; Wong 1982, Brouwer et al. 1989, p. 209). It has girth 7, diameter 4, and chromatic number 3.

McGeeGraph2

A symmetric embedding is illustrated above.

McGeeGraph

The McGee graph is Hamiltonian and has a single distinct LCF notation of order 8, [-12,7,-7]^8, one of order 2, and two of order 1, all illustrated above.

Its automorphism group is of size 32 and it has graph spectrum

1/2(-1-sqrt(17))alpha^4(-2)(-1)^2beta^40^31/2(-1+sqrt(17))gamma^42^33,

where alpha, beta, and gamma are the roots of x^3+x^2-4x-2.

McGeeGraphCrossings

The McGee graph has rectilinear crossing number 8, as established by G. Exoo around 1990 (G. Exoo, pers. comm., May 12, 2019). It is one of three cubic graphs on 24 nodes with smallest possible graph crossing number of 8 (another being the Nauru graph), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).

The graph is not vertex-transitive (Holton and Sheehan 1993, pp. 207-208) since its automorphism group has orbits of length 8 and 16. It is therefore also not 4-transitive (as incorrectly stated by Harary 1994, p. 175).

It is implemented in the Wolfram Language as GraphData["McGeeGraph"].

See also

Cage Graph, Cubic Symmetric Graph, Nauru Graph, Smallest Cubic Crossing Number Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Exoo, G. "Rectilinear Drawings of Famous Graphs: The McGee Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/mcgee.gif.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.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.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 271, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.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.

Cite this as:

Weisstein, Eric W. "McGee Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/McGeeGraph.html

Subject classifications