Tutte 12-cage


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 named after W. T. Tutte.
The Tutte 12-cage is the unique -cage. It was discovered by C. T. Benson in 1966. It has chromatic number 2, chromatic index 3, girth 12 and diameter 6. Its crossing number is 170 and has been conjectured to be the smallest cubic graph with this crossing number.

Construction

The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation 7.
There are, up to isomorphism, precisely two generalized hexagons of order as proved by Cohen and Tits. They are the split Cayley hexagon H 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 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.
The characteristic polynomial of the Tutte 12-cage is
It is the only graph with this characteristic polynomial; therefore, the 12-cage is determined by its spectrum.

Gallery