View source for Coxeter graph

{{Short description|Cubic graph with 28 vertices and 42 edges}}
{{About|the 3-regular graph|the graph associated with a Coxeter group|Coxeter diagram}}
{{Distinguish|Tutte-Coxeter graph}}
{{Infobox graph
 | name = Coxeter graph
 | image = [[Image:Coxeter graph.svg|250px]]
 | image_caption = The Coxeter graph
 | namesake = [[H. S. M. Coxeter]]
 | vertices = 28
 | edges = 42
 | automorphisms= 336 ([[Projective linear group|PGL]]<sub>2</sub>(7))
 | girth = 7
 | diameter = 4
 | radius = 4
 | chromatic_number = 3
 | chromatic_index = 3
 | properties = [[Symmetric graph|Symmetric]]<br>[[distance-regular graph|Distance-regular]]<br>[[distance-transitive graph|Distance-transitive]]<br>[[Cubic graph|Cubic]]<br>[[Hypohamiltonian graph|Hypohamiltonian]]
|book thickness=3|queue number=2}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Coxeter graph''' is a 3-[[regular graph]] with 28 vertices and 42 edges.<ref>{{MathWorld|urlname=CoxeterGraph|title=Coxeter Graph}}</ref> It is one of the 13 known [[cubic graph|cubic]] [[distance-regular graph]]s.<ref>Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.</ref> It is named after [[Harold Scott MacDonald Coxeter]].

==Properties==
The Coxeter graph has [[chromatic number]] 3, [[chromatic index]] 3, radius 4, diameter 4 and [[girth (graph theory)|girth]] 7. It is also a 3-[[k-vertex-connected graph|vertex-connected graph]] and a 3-[[k-edge-connected graph|edge-connected graph]]. It has [[book thickness]] 3 and [[queue number]] 2.<ref>Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018</ref>

The Coxeter graph is [[hypohamiltonian graph|hypohamiltonian]]: it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It has [[Crossing number (graph theory)|rectilinear crossing number]] 11, and is the smallest cubic graph with that crossing number<ref>{{citation|first1=Michael|last1=Haythorpe|first2=Alex|last2=Newcombe|title=There are no Cubic Graphs on 26 Vertices with Crossing Number 11|year=2018|arxiv=1804.10336}}</ref> {{OEIS|id=A110507}}.

==Construction==
The simplest construction of a Coxeter graph is from a [[Fano plane]]. Take the [[Combination|<sup>7</sup>C<sub>3</sub>]] = 35 possible 3-combinations on 7 objects. Discard the 7 triplets that correspond to the lines of the Fano plane, leaving 28 triplets. Link two triplets if they are disjoint. The result is the Coxeter graph. <small>(See [[c:File:Coxeter graph with Fano plane vertices.svg|image]].)</small> This construction exhibits the Coxeter graph as an [[induced subgraph]] of the [[odd graph]] O<sub>4</sub>, also known as the [[Kneser graph]] {{math|''KG''<sub>7,3</sub>}}.

The Coxeter graph may also be constructed from the smaller distance-regular [[Heawood graph]] by constructing a vertex for each 6-cycle in the Heawood graph and an edge for each disjoint pair of 6-cycles.<ref>{{citation|first=Italo J.|last=Dejter|title=From the Coxeter graph to the Klein graph|journal=[[Journal of Graph Theory]]|year=2011|volume=70|pages=1–9|doi=10.1002/jgt.20597|arxiv=1002.1960|s2cid=754481}}.</ref>

The Coxeter graph may be derived from the [[Hoffman-Singleton graph]]. Take any vertex ''v'' in the Hoffman-Singleton graph. There is an [[independent set (graph theory)|independent set]] of size 15 that includes ''v''. Delete the 7 neighbors of ''v'', and the whole independent set including ''v'', leaving behind the Coxeter graph.

==Algebraic properties==
The automorphism group of the Coxeter graph is a group of order 336.<ref>Royle, G. [https://web.archive.org/web/20070907083032/http://people.csse.uwa.edu.au/gordon/remote/foster/F028A.html F028A data]</ref> It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Coxeter graph is a [[symmetric graph]]. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Coxeter graph, referenced as F28A, is the only cubic symmetric graph on 28 vertices.<ref>[[Marston Conder|Conder, M.]] and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.</ref>

The Coxeter graph is also uniquely determined by its [[graph spectrum]], the set of graph eigenvalues of its [[adjacency matrix]].<ref>E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189-202, 2003</ref>

As a finite connected vertex-transitive graph that contains no [[Hamiltonian cycle]], the Coxeter graph is a counterexample to a variant of the [[Lovász conjecture]], but the canonical formulation of the conjecture asks for an Hamiltonian path and is verified by the Coxeter graph.

Only five examples of vertex-transitive graph with no Hamiltonian cycles are known : the [[complete graph]] ''K''<sub>2</sub>, the [[Petersen graph]], the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.<ref>Royle, G. [http://staffhome.ecm.uwa.edu.au/~00013890/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."] {{Webarchive|url=https://web.archive.org/web/20150912020037/http://staffhome.ecm.uwa.edu.au/~00013890/remote/foster/#census |date=2015-09-12 }}</ref>

The [[characteristic polynomial]] of the Coxeter graph is <math>(x-3) (x-2)^8 (x+1)^7 (x^2+2 x-1)^6</math>. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

==Gallery==

===Layouts===

These are different representations of the Coxeter graph, using the same vertex labels. There are four colors, and seven vertices of each color.<br>
Each red, green or blue vertex is connected with two vertices of the same color (thin edges forming 7-cycles) and to one white vertex (thick edges).

{|
|- style="vertical-align: top;"
| 
{{multiple image
 | align = left  | total_width = 427
 | image1 = Coxeter graph RGBW 7 central.svg
 | image2 = Coxeter graph RGBW 7 separate.svg
 | footer = red [[heptagon]], green obtuse and blue acute [[heptagram]]<br><small>left: 7-fold rotational symmetry</small>
}}
| [[File:Coxeter graph RGBW 24.svg|thumb|left|x200px|in [[Icositetragon|24-gon]]<br><small>3-fold rotational symmetry</small>]]
| [[File:Coxeter graph RGBW 6.svg|thumb|left|x200px|<small>3-fold dihedral symmetry<br>(compare [[c:File:Coxeter graph with Fano plane vertices.svg|variant with Fano plane vertices]])</small>]]
| [[File:Coxeter graph RGBW 8.svg|thumb|left|x200px|in [[octagon]]<br><small>mirror symmetry</small>]]
|}


===Properties===
{|
|- style="vertical-align: top;"
| [[File:Edge excised Coxeter graph.svg|thumb|left|The graph obtained by any edge excision from the Coxeter is Hamilton-connected.]]
| [[File:coxeter_graph_3COL.svg|thumb|left|The [[chromatic number]] of the Coxeter graph is&nbsp;3.]]
| [[File:Coxeter graph 11C.svg|thumb|left|The [[Crossing number (graph theory)|rectilinear crossing number]] of the Coxeter graph is&nbsp;11.]]
| [[File:Coxeter one planar.svg|thumb|left|The Coxeter graph is [[1-planar_graph|1-planar]].]]
|}

== References ==
{{Reflist}}

* Coxeter, H. S. M. "My Graph." Proc. London Math. Soc. 46, 117-136, 1983.

{{Authority control}}

[[Category:Individual graphs]]
[[Category:Regular graphs]]