TOPICS
Search

Tutte 8-Cage


LeviGraph

The Tutte 8-cage (Godsil and Royle 2001, p. 59; right figure) is a cubic graph on 30 nodes and 45 edges which is the Levi graph of the Cremona-Richmond configuration. It consists of the union of the two leftmost subgraphs illustrated above. The Tutte 8-cage is the unique (3,8)-cage graph and Moore graph. It is also a generalized polygon which is the point/line Levi graph of the generalized quadrangle W_2 and its line graph is the generalized octagon GO(2,1). The graph was first discovered by Tutte (1947) and is also called the Tutte-Coxeter graph (Bondy and Murty 1976, p. 237; Brouwer et al. 1989, p. 209) or Tutte's cage (Read and Wilson 1998, p. 271).

LeviGraphEmbeddings

The Tutte 8-cage is illustrated above in a number of embeddings.

The Tutte 8-cage graph has rectilinear crossing number 13, as established by G. Exoo around 1990 (G. Exoo, pers. comm., May 12, 2019). It is the smallest known cubic graph with graph crossing number of 13, making it likely a smallest cubic crossing number graph, though as of May 2019 this has not yet been definitively established (Pegg and Exoo 2009, Clancy et al. 2019).

It is 4-arc transitive, has girth 8, diameter 4, chromatic number 2, and automorphism group order 1440. It is also distance-regular and distance-transitive with intersection array {3,2,2,2;1,1,1,3}. The Tutte 8-cage graph is an integral graph with graph spectrum (-3)^1(-2)^90^(10)2^93^1. It can be represented in LCF notation as [-13,-9,7,-7,9,13]^5 (Frucht 1976).

LeviGraphUnitDistance

It is also a unit-distance graph (Gerbracht 2008), as illustrated above in a number of unit-distance embeddings (E. Gerbracht, pers. comm., Jan. 2010).

The Tutte 8-cage is implemented in the Wolfram Language as GraphData["Tutte8Cage"].


See also

Cage Graph, Configuration, Integral Graph, Moore Graph, Smallest Cubic Crossing Number Graph, Tutte 12-Cage

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 237 and 276, 1976.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Coxeter, H. S. M. "The Chords of the Non-Ruled Quadratic in PG(3,3)." Canad. J. Math. 10, 484-488, 1958.Coxeter, H. S. M. "Twelve Points in PG(5,3) with 95040 Self-Transformations." Proc. Roy. Soc. London Ser. A 247, 279-293, 1958.DistanceRegular.org. "Tutte's 8-Cage." http://www.distanceregular.org/graphs/tutte8.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Tutte 8-Cage." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/tutte.gif.Frucht, R. "A Canonical Representation of Trivalent Hamiltonian Graphs." J. Graph Th. 1, 45-60, 1976.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 271, 1998.Update a linkRoyle, G. "F030A." http://www.csse.uwa.edu.au/~gordon/foster/F030A.htmlUpdate a linkRoyle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc., 459-474, 1947.Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966.Tutte, W. T. "The Chords of the Non-Ruled Quadratic in PG(3,3)." Canad. J. Math. 10, 481-483, 1958.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Cite this as:

Weisstein, Eric W. "Tutte 8-Cage." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tutte8-Cage.html

Subject classifications