| Tutte 12-cage | |
| Vertices: | 126 |
| Edges: | 189 |
| Automorphisms: | 12096 |
| Genus: | 17 |
| Girth: | 12 |
| Radius: | 6 |
| Diameter: | 6 |
| 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 is a 3-regular graph with 126 vertices and 189 edges. It is named after W. T. Tutte.
The Tutte 12-cage is the unique (3-12)-cage . It was discovered by C. T. Benson in 1966.[1] 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.[2] [3]
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.[4]
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.[5]
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.[6] 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.[7]
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.[8]
The characteristic polynomial of the Tutte 12-cage is
(x-3)x28(x+3)(x2-6)21(x2-2)27.
It is the only graph with this characteristic polynomial; therefore, the 12-cage is determined by its spectrum.