In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges.[1]
| McGee graph | |
|---|---|
 The McGee graph | |
| Named after | W. F. McGee |
| Vertices | 24 |
| Edges | 36 |
| Radius | 4 |
| Diameter | 4[1] |
| Girth | 7[1] |
| Automorphisms | 32[1] |
| Chromatic number | 3[1] |
| Chromatic index | 3[1] |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Cubic Cage Hamiltonian |
| Table of graphs and parameters | |
The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph.
First discovered by Sachs but unpublished,[2] the graph is named after McGee who published the result in 1960.[3] Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.[4][5][6]
The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph.[7][8]
The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3-vertex-connected and a 3-edge-connected graph. It has book thickness 3 and queue number 2.[9]
Algebraic properties
editThe characteristic polynomial of the McGee graph is
- .
The automorphism group of the McGee graph is of order 32 and doesn't act transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a vertex-transitive graph.[10]
Gallery
edit-
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. -
Alternative drawing of the McGee graph.
References
edit- ^ a b c d e f 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. (1960). "A Minimal Cubic Graph of Girth Seven". Canadian Mathematical Bulletin. 3 (2): 149–152. doi:10.4153/CMB-1960-018-1.
- ^ Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
- ^ Wong, Pak-Ken (1982). "Cages—A Survey". Journal of Graph Theory. 6: 1–22. doi:10.1002/jgt.3190060103.
- ^ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
- ^ Sloane, N. J. A. (ed.). "Sequence A110507 (Number of nodes in the smallest cubic graph with crossing number n)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- ^ Pegg, E. T.; Exoo, G. (2009). "Crossing number graphs". Mathematica Journal. 11 (2). doi:10.3888/tmj.11.2-2..
- ^ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- ^ Jajcay, Robert; Širáň, Jozef (2011). "Small vertex-transitive graphs of given degree and girth". Ars Mathematica Contemporanea. 4 (2): 375–384. doi:10.26493/1855-3974.124.06d.