McGee graph

{{infobox graph

| name = McGee graph

| image = 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}}

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.{{MathWorld|urlname=McGeeGraph|title=McGee Graph}}

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,Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960 the graph is named after McGee who published the result in 1960.{{cite journal

| last1=McGee | first1=W. F.

| title=A Minimal Cubic Graph of Girth Seven

| journal=Canadian Mathematical Bulletin

| volume=3

| issue=2

| pages=149–152

| date=1960

| doi=10.4153/CMB-1960-018-1 | doi-access=free}} Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966{{cite journal

| last1=Wong | first1=Pak-Ken

| title=Cages—A Survey

| journal=Journal of Graph Theory

| volume=6

| pages=1–22

| date=1982

| doi=10.1002/jgt.3190060103}}Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989

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 {{nobr|G(12,5)}}, also known as the Nauru graph. {{Cite OEIS|1=A110507|2=Number of nodes in the smallest cubic graph with crossing number n}}{{cite journal|last1=Pegg|first1=E. T.|authorlink=Ed Pegg, Jr.|last2=Exoo|first2=G.|title=Crossing number graphs|journal=Mathematica Journal|volume=11|year=2009|issue=2 |doi=10.3888/tmj.11.2-2 |url=http://www.mathematica-journal.com/issue/v11i2/CrossingNumberGraphs.html|doi-access=free}}.

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.Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018

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

| last1 = Jajcay | first1 = Robert

| last2 = Širáň | first2 = Jozef

| doi = 10.26493/1855-3974.124.06d

| issue = 2

| journal = Ars Mathematica Contemporanea

| pages = 375–384

| title = Small vertex-transitive graphs of given degree and girth

| volume = 4

| year = 2011| doi-access = free

}}

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$ .John C. Baez, What algebraic structures are related to the McGee graph?, https://mathoverflow.net/q/215211 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

Category:Individual graphs

Category:Regular graphs