TOPICS
Search

Coxeter Graph


CoxeterGraph

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 7S_4 with steps 1, 2, and 4, where S_4=K_(1,3) is the claw graph (Biggs 1993, p. 147). It is denoted F_(028)A in the Foster census of cubic symmetric graphs. It is distance-regular and distance-transitive with intersection array {3,2,2,1;1,1,1,2}.

CoxeterGraphEmbeddings

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 (-1-sqrt(2))^6(-1)^7(sqrt(2)-1)^62^83^1 (van Dam and Haemers 2002).

The bipartite double graph of the Coxeter graph is the cubic symmetric graph F_(056)C.

CoxeterGraphUnitDistance

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"].

CoxeterGraphVariants

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"].


See also

Cospectral Graphs, Coxeter-Dynkin Diagram, Cubic Symmetric Graph, Determined by Spectrum, Smallest Cubic Crossing Number Graph, Tutte 8-Cage

Explore with Wolfram|Alpha

References

Bondy, J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 241, 1976.Brouwer, A. E. "Coxeter Graph." http://www.win.tue.nl/~aeb/drg/graphs/Coxeter.html.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.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. "My Graph." Proc. London Math. Soc. 46, 117-136, 1983.DistanceRegular.org. "Coxeter Graph." http://www.distanceregular.org/graphs/coxeter.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Coxeter Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/coxeter.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.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.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Royle, G. "F028A." http://www.csse.uwa.edu.au/~gordon/foster/F028A.html.Tutte, W. T. "A Non-Hamiltonian Graph." Canad. Math. Bull. 3, 1-5, 1960.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

Cite this as:

Weisstein, Eric W. "Coxeter Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CoxeterGraph.html

Subject classifications