From Surf Wiki (app.surf) — the open knowledge base

McGee graph

Graph with 24 vertices and 36 edges

Field	Value
name	McGee graph
image	[[Image: McGee graph hamiltonian.svg	220px]]
image_caption	The McGee graph
namesake	W. F. McGee
vertices	24
edges	36
automorphisms	32
girth	7
diameter	4
radius	4
chromatic_number	3
chromatic_index	3
properties	Cubic
Cage
Hamiltonian
book thickness	3	queue number=2

Cage Hamiltonian 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.

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, the graph is named after McGee who published the result in 1960.{{cite journal

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 , also known as the Nauru graph.

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. The graph is 1-planar.{{citation | editor-first1 = Vida | editor-last1 = Dujmović | editor-first2 = Fabrizio | editor-last2 = Montecchiani

Algebraic properties

The characteristic polynomial of the McGee graph is :x^3(x-3)(x-2)^3(x+1)^2(x+2)(x^2+x-4)(x^3+x^2-4x-2)^4.

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.{{cite journal

The automorphism group of the McGee graph, meaning its group of symmetries, has 32 elements. This group is isomorphic to the group of all affine transformations of \mathbb{Z}/8\mathbb{Z}, i.e., transformations of the form

:: x \mapsto ax + b

where a,b \in \mathbb{Z}/8\mathbb{Z} and a is invertible, so a = 1, 3, 5, 7. This is one of the two smallest possible group G with an outer automorphism that maps every element g \in G to an element conjugate to g. Peter A. Brooksbank and Matthew S. Mizuhara (2014). On groups with a class-preserving outer automorphism, Involve. Vol. 7, No. 2, 171–179. doi:10.2140/involve.2014.7.171 https://msp.org/involve/2014/7-2/p04.xhtml

Gallery

Image:McGee graph crossing number.svg|The crossing number of the McGee graph is 8. Image:McGee graph 3COL.svg |The chromatic number of the McGee graph is 3. Image:McGee graph 3color edge.svg|The chromatic index of the McGee graph is 3. Image:Acyclic_coloring.svg|The acyclic chromatic number of the McGee graph is 3. Image:McGee graph.svg|Alternative drawing of the McGee graph.

References

"McGee Graph".
Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
{{Cite OEIS
(2009). "Crossing number graphs". Mathematica Journal.
Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018
John C. Baez, What algebraic structures are related to the McGee graph?, https://mathoverflow.net/q/215211

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

individual-graphs regular-graphs

Want to explore this topic further?

Ask Mako anything about McGee graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report