McGee graph
| 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 | |
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]
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
The characteristic polynomial of the McGee graph is
- [math]\displaystyle{ x^3(x-3)(x-2)^3(x+1)^2(x+2)(x^2+x-4)(x^3+x^2-4x-2)^4 }[/math].
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
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
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Weisstein, Eric W.. "McGee Graph". http://mathworld.wolfram.com/McGeeGraph.html.
- ↑ 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)". OEIS Foundation. https://oeis.org/A110507.
- ↑ Pegg, E. T.; Exoo, G. (2009). "Crossing number graphs". Mathematica Journal 11 (2). doi:10.3888/tmj.11.2-2. http://www.mathematica-journal.com/issue/v11i2/CrossingNumberGraphs.html..
- ↑ 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.
 |  |
