McGee graph

Last updated
McGee graph
McGee graph hamiltonian.svg
The McGee graph
Named afterW. 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]

Contents

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

.

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]

Related Research Articles

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Heawood graph</span> Undirected graph with 14 vertices

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

<span class="mw-page-title-main">Tutte–Coxeter graph</span>

In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle W2. The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers.

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

<span class="mw-page-title-main">Semi-symmetric graph</span> Graph that is edge-transitive and regular but not vertex-transitive

In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second.

<span class="mw-page-title-main">Coxeter graph</span> Type of graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

<span class="mw-page-title-main">Pappus graph</span> Bipartite, 3-regular undirected graph

In the mathematical field of graph theory, the Pappus graph is a bipartite, 3-regular, undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic, distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.

<span class="mw-page-title-main">Grötzsch graph</span> Triangle-free graph requiring four colors

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.

<span class="mw-page-title-main">Cage (graph theory)</span> Regular graph with fewest possible nodes for its girth

In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

<span class="mw-page-title-main">Crossing number (graph theory)</span> Fewest edge crossings in drawing of a graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

<span class="mw-page-title-main">Tietze's graph</span> Undirected cubic graph with 12 vertices and 18 edges

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.

<span class="mw-page-title-main">Chvátal graph</span>

In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970. It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic.

<span class="mw-page-title-main">Nauru graph</span> 24-vertex symmetric bipartite cubic graph

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

<span class="mw-page-title-main">F26A graph</span>

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

<span class="mw-page-title-main">Brinkmann graph</span>

In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997.

<span class="mw-page-title-main">Tutte 12-cage</span>

In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges. It is named after W. T. Tutte.

<span class="mw-page-title-main">Tutte graph</span>

In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.

<span class="mw-page-title-main">Klein graphs</span>

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

<span class="mw-page-title-main">110-vertex Iofinova–Ivanov graph</span> Semi-symmetric cubic graph with 110 vertices and 165 edges

The 110-vertex Iofinova–Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.

References

  1. 1 2 3 4 5 6 Weisstein, Eric W. "McGee Graph". MathWorld .
  2. Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
  3. 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 .
  4. Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
  5. Wong, Pak-Ken (1982). "Cages—A Survey". Journal of Graph Theory . 6: 1–22. doi:10.1002/jgt.3190060103.
  6. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
  7. Sloane, N. J. A. (ed.). "SequenceA110507(Number of nodes in the smallest cubic graph with crossing number n)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
  8. Pegg, E. T.; Exoo, G. (2009). "Crossing number graphs". Mathematica Journal. 11 (2). doi: 10.3888/tmj.11.2-2 ..
  9. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  10. 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.