Coxeter Graph

The Coxeter graph is a nonhamiltonian cubic symmetric graph on 28 vertices and 42 edges which can be constructed as illustrated above. It can also be constructed as the graph expansion of with steps 1, 2, and 4, where is the claw graph (Biggs 1993, p. 147). It is denoted in the Foster census of cubic symmetric graphs. It is distance-regular and distance-transitive with intersection array .

A number of embeddings are illustrated above (e.g., Read and Wilson 1998, p. 162).

The Coxeter graph has rectilinear crossing number 11, as established by G. Exoo around 1990 (G. Exoo, pers. comm., May 12, 2019). It is a cubic graph on 28 nodes with smallest possible graph crossing number of 11, making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).

As first shown by Bondy (1972), it is also hypohamiltonian.

The Coxeter graph is determined by its spectrum (van Dam and Haemers 2002).

The bipartite double graph of the Coxeter graph is the cubic symmetric graph .

It is also a unit-distance graph, as illustrated in the above unit-distance embedding (Gerbracht 2008, pers. comm., Jan. 4, 2010).

The Coxeter graph is implemented in the Wolfram Language as GraphData["CoxeterGraph"].

If any edge is excised from the Coxeter graph, the resulting graph is the Hamilton-connected graph (left figure above) which is implemented in the Wolfram Language as GraphData["EdgeExcisedCoxeterGraph"]. The triangle-replaced Coxeter graph (right figure above) appears as an exceptional graph in conjectures about nonhamiltonian vertex-transitive graphs, H-*-connected graphs, and Hamilton decompositions. It is implemented in the Wolfram Language as GraphData["TriangleReplacedCoxeterGraph"].