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

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 170 and has been conjectured to be the smallest cubic graph with this crossing number.^[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.

References

1. 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." Canad. 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.