Tutte–Coxeter graph

Tutte–Coxeter graph
Named after	W. T. Tutte H. S. M. Coxeter
Vertices	30
Edges	45
Diameter	4
Girth	8
Automorphisms	1440 (Aut(S6))
Chromatic number	2
Chromatic index	3
Properties	Cubic Cage Moore graph Symmetric Distance-regular Distance-transitive Bipartite
Table of graphs and parameters

In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8 it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle W₂ (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a).

All the cubic distance-regular graphs are known. The Tutte–Coxeter is one of the 13 such graphs.

Duads, synthemes, and automorphisms

A particularly simple combinatorial construction of the Tutte–Coxeter graph is due to Coxeter (1958b), based on much earlier work by Sylvester (1844). From a set of six elements (for instance the letters a,b,c,d,e,f) Sylvester defined a duad to be one of the 15 unordered pairs of elements: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, or ef. He also defined a syntheme to be one of the 15 partitions of the elements into three duads: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, be, df); (ac, bf, de); (ad, bc, ef); (ad, be, cf); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Each syntheme contains three duads, and each duad belongs to three synthemes. The Tutte–Coxeter graph can be viewed as having one vertex per duad, one vertex per syntheme, and an edge connecting each syntheme to each of the three duads that form it.

Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph; it has a group of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six elements from which we defined the morphemes and synthemes; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the outer automorphisms of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte–Coxeter graph is equivalent to any other such path by one such automorphism.

Gallery

• 
  The crossing number of the Tutte–Coxeter graph is 13.
• 
  The chromatic number of the Tutte–Coxeter graph is 2.
• 
  The chromatic index of the Tutte–Coxeter graph is 3.

References

• Coxeter, H. S. M. (1958a). "The chords of the non-ruled quadric in PG(3,3)". Canad. J. Math. 10: 484–488. doi:10.4153/CJM-1958-047-0.

• Coxeter, H. S. M. (1958b). "Twelve points in PG(5,3) with 95040 self-transformations". Proceedings of the Royal Society A. 247 (1250): 279–293. doi:10.1098/rspa.1958.0184. JSTOR 100667.

• Sylvester, J. J. (1844). "Elementary researches in the analysis of combinatorial aggregation". The Philos. Mag., Series 3. 24: 285–295.

• Tutte, W. T. (1947). "A family of cubical graphs". Proc. Cambridge Philos. Soc. 43 (04): 459–474. doi:10.1017/S0305004100023720.

• Tutte, W. T. (1958). "The chords of the non-ruled quadric in PG(3,3)". Canad. J. Math. 10: 481–483. doi:10.4153/CJM-1958-046-3.

External links

• François Labelle. "3D Model of Tutte's 8-cage".
• Weisstein, Eric W. "Levi Graph". MathWorld.
• Exoo, G. "Rectilinear Drawings of Famous Graphs." [1]