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 GH(2,2) and alternately called the generalized hexagon GH(1,2), 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 (+/-3)^10^(28)(+/-sqrt(2))^(27)(+/-sqrt(6))^(21) and has LCF notation [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17]^7 (Polster 1998). It is determined by spectrum.

It is distance-regular with intersection array {3,2,2,2,2,2;1,1,1,1,1,3} 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 GH(2,2) 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.

See also

Balaban 11-Cage, Cage Graph, Cubic Semisymmetric Graph, Determined by Spectrum, Generalized Hexagon, Iofinova-Ivanov Graphs, Tutte 8-Cage, Tutte's Graph

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha


Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 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., A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, "Tutte's 12-Cage = Incidence Graph of GH(2,2).", G. "Rectilinear Drawings of Famous Graphs: The 12-Cage.", 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.", 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.

Cite this as:

Pegg, Ed Jr. and Weisstein, Eric W. "Tutte 12-Cage." From MathWorld--A Wolfram Web Resource.

Subject classifications