Tutte 12-Cage

The Tutte 12-cage, also called the Benson graph (Exoo and Jajcay 2008), is the unique 12-cage graph, equivalent to the generalized hexagon and alternately called the generalized hexagon , as studied by Tits (1959). The first implicit description as a graph seems to be by Benson (1966), but it is most frequently called the Tutte 12-cage (Brouwer 1989).

It has 126 vertices (all cubic), 189 edges, girth 12 (by definition), and diameter 6. It has graph spectrum and has LCF notation [17, 27, , , , 35, , 13, , 53, , 21, 57, 11, , , 59, (Polster 1998). It is determined by spectrum.

It is distance-regular with intersection array but is not distance-transitive.

An embedding with rectilinear crossing number 166 was found by G. Exoo (pers. comm., May 12, 2019) which QuickCross was able to reduce to a graph crossing number of 165 (E. Weisstein, May 12, 2019).

It is the point-line Levi graph of the generalized hexagon with 63 points and 63 lines (A. E. Brouwer, pers. comm., Jun. 8, 2009).

It is the largest cubic distance-regular graph, but is not a cubic symmetric graph (Brouwer 1989). However, it is one of the five Iofinova-Ivanov graphs (i.e., bipartite cubic semisymmetric graphs whose automorphism groups preserve the bipartite parts and act primitively on each part). It is also the first in an infinite family of biprimitive graphs and was described by Biggs (1974, p. 164) in terms of the projective plane of order 9 equipped with a unitary form (Iofinova and Ivanov 1985).

In 1973, Balaban excised a tree consisting of two adjacent vertices and the twelve vertices within distance 2 to obtain the unique Balaban 11-cage.