Tutte 12-cage

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]7.

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.

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.

Algebraic properties

The automorphism group of the Tutte 12-cage is of order and is a semi-direct product of the projective special unitary group PSU(3,3) with the cyclic group Z/2Z. 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.

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.{{citation

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

Image:Tutte 12-cage 2COL.svg|The chromatic number of the Tutte 12-cage is 2. Image:Tutte 12-cage 3color edge.svg|The chromatic index of the Tutte 12-cage is 3.

References

References

1. "Tutte 12-cage".
2. Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Can. J. Math. 18, 1091–1094, 1966.
3. Exoo, G. [http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ "Rectilinear Drawings of Famous Graphs"].
4. Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
5. Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
6. Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.
7. Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
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.)