Tutte 12-cage

Tutte 12-cage
Tutte 12-cage
	The Tutte 12-cage
Named after	W. T. Tutte
Vertices	126
Edges	189
Radius	6
Diameter	6
Girth	12
Automorphisms	12096
Chromatic number	2
Chromatic index	3
Properties	Cubic ; Cage ; Hamiltonian ; Semi-symmetric ; Bipartite
	Table of graphs and parameters

Last updated February 28, 2023

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

The Tutte 12-cage is the unique (3-12)-cage (sequence A052453 in the OEIS ). It was discovered by C. T. Benson in 1966.^[3] It has chromatic number 2 (bipartite), chromatic index 3, girth 12 (as a 12-cage) and diameter 6. Its crossing number is known to be less than 165, see Wolfram MathWorld. ^[4]^[5]

Construction

The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17]⁷.^[6]

There are, up to isomorphism, precisely two generalized hexagons of order (2,2) as proved by Cohen and Tits. They are the split Cayley hexagon H(2) and its point-line dual. Clearly both of them have the same incidence graph, which is in fact isomorphic to the Tutte 12-cage.^[1]

The Balaban 11-cage can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.^[7]

Algebraic properties

The automorphism group of the Tutte 12-cage is of order 12,096 and is a semi-direct product of the projective special unitary group PSU(3,3) with the cyclic group Z/2Z.^[1] It acts transitively on its edges but not on its vertices, making it a semi-symmetric graph, a regular graph that is edge-transitive but not vertex-transitive. In fact, the automorphism group of the Tutte 12-cage preserves the bipartite parts and acts primitively on each part. Such graphs are called bi-primitive graphs and only five cubic bi-primitive graphs exist; they are named the Iofinova-Ivanov graphs and are of order 110, 126, 182, 506 and 990.^[8]

All the cubic semi-symmetric graphs on up to 768 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the Tutte 12-cage is the unique cubic semi-symmetric graph on 126 vertices and is the fifth smallest possible cubic semi-symmetric graph after the Gray graph, the Iofinova–Ivanov graph on 110 vertices, the Ljubljana graph and a graph on 120 vertices with girth 8.^[9]

The characteristic polynomial of the Tutte 12-cage is

(x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}.\

It is the only graph with this characteristic polynomial; therefore, the 12-cage is determined by its spectrum.

Gallery

The chromatic number of the Tutte 12-cage is 2.
The chromatic index of the Tutte 12-cage is 3.

Related Research Articles

Dragan Marušič is a Slovene mathematician. Marušič obtained his BSc in technical mathematics from the University of Ljubljana in 1976, and his PhD from the University of Reading in 1981 under the supervision of Crispin Nash-Williams.

In the mathematical field of graph theory, an edge-transitive graph is a graph $G$ such that, given any two edges $e 1$ and $e 2$ of $G$ , there is an automorphism of $G$ that maps $e 1$ to $e 2$ .

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.

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 W₂. 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.

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.

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges.

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.

In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban.

In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.

In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.

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.

In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.

In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.

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

In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981 respectively.

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.

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

References

1 2 3 Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
↑ Weisstein, Eric W. "Tutte 12-cage". MathWorld .
↑ Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Can. J. Math. 18, 1091–1094, 1966.
↑ Exoo, G. "Rectilinear Drawings of Famous Graphs".
↑ Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
↑ Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
↑ Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.
↑ Iofinova, M. E. and Ivanov, A. A. "Bi-Primitive Cubic Graphs." In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137–152, 1985.)
↑ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23: 255–294, doi: 10.1007/s10801-006-7397-3 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[SURV-1] 1 2 3 Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).

[2] Weisstein, Eric W. "Tutte 12-cage". MathWorld .

[3] Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Can. J. Math. 18, 1091–1094, 1966.

[4] Exoo, G. "Rectilinear Drawings of Famous Graphs".

[5] Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.

[6] Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.

[7] Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.

[8] Iofinova, M. E. and Ivanov, A. A. "Bi-Primitive Cubic Graphs." In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137–152, 1985.)

[9] Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23: 255–294, doi: 10.1007/s10801-006-7397-3 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]