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).
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.
Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math18,
1033-1043, 1973.Benson, C. T. "Minimal Regular Graphs of Girth
8 and 12." Canad. J. Math.18, 1091-1094, 1966.Biggs,
N. L. Algebraic
Graph Theory. Cambridge, England: Cambridge University Press, p. 164,
1974.Biggs, N. "Constructions for Cubic Graphs with Large Girth."
Elec. J. Combin.5, Aug. 31, 1998. http://citeseer.ist.psu.edu/biggs98constructions.html.Brouwer,
A. E.; Cohen, A. M.; and Neumaier, A. Distance
Regular Graphs. New York: Springer-Verlag, 1989.DistanceRegular.org.
"Tutte's 12-Cage
Incidence Graph of ."
http://www.distanceregular.org/graphs/tutte12.html.Exoo,
G. "Rectilinear Drawings of Famous Graphs: The 12-Cage." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/cage12.gif.Exoo,
G. and Jajcay, R. "Dynamic Cage Survey." Electr. J. Combin.15,
2008.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.)Polster, B. A
Geometrical Picture Book. New York: Springer, p. 179, 1998.Royle,
G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Tits,
J. "Sur la trialité et certains groupes qui s'en déduisent."
Inst. Hautes Etudes Sci. Publ. Math.2, 14-60, 1959.Wong,
P. K. "Cages--A Survey." J. Graph Th.6, 1-22, 1982.