Coxeter graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges.[1] It is one of the 13 known cubic distance-regular graphs.[2] It is named after Harold Scott MacDonald Coxeter.

This article is about the 3-regular graph. For the graph associated with a Coxeter group, see Coxeter diagram.
Not to be confused with Tutte-Coxeter graph.
Coxeter graph
The Coxeter graph
Named afterH. S. M. Coxeter
Vertices28
Edges42
Radius4
Diameter4
Girth7
Automorphisms336 (PGL2(7))
Chromatic number3
Chromatic index3
Book thickness3
Queue number2
PropertiesSymmetric
Distance-regular
Distance-transitive
Cubic
Hypohamiltonian
Table of graphs and parameters

Properties

The Coxeter graph has chromatic number 3, chromatic index 3, radius 4, diameter 4 and girth 7. It is also a 3-vertex-connected graph and a 3-edge-connected graph. It has book thickness 3 and queue number 2.[3]

The Coxeter graph is hypohamiltonian: it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It has rectilinear crossing number 11, and is the smallest cubic graph with that crossing number[4] (sequence A110507 in the OEIS).

Construction

The simplest construction of a Coxeter graph is from a Fano plane. Take the 7C3 = 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. (See image.) This construction exhibits the Coxeter graph as an induced subgraph of the odd graph O4, also known as the Kneser graph KG7,3.

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.[5]

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 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.[6] 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.[7]

The Coxeter graph is also uniquely determined by its graph spectrum, the set of graph eigenvalues of its adjacency matrix.[8]

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 K2, the Petersen graph, the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.[9]

The characteristic polynomial of the Coxeter graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

Layouts

These are different representations of the Coxeter graph, using the same vertex labels. There are four colors, and seven vertices of each color.
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).

red heptagon, green obtuse and blue acute heptagram
left: 7-fold rotational symmetry
in 24-gon
3-fold rotational symmetry
3-fold dihedral symmetry
(compare variant with Fano plane vertices)
in octagon
mirror symmetry


Properties
The graph obtained by any edge excision from the Coxeter is Hamilton-connected.
The chromatic number of the Coxeter graph is 3.
The rectilinear crossing number of the Coxeter graph is 11.

References
  1. Weisstein, Eric W. "Coxeter Graph". MathWorld.
  2. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
  3. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  4. Haythorpe, Michael; Newcombe, Alex (2018), There are no Cubic Graphs on 26 Vertices with Crossing Number 11, arXiv:1804.10336
  5. Dejter, Italo J. (2011), "From the Coxeter graph to the Klein graph", Journal of Graph Theory, 70: 1–9, arXiv:1002.1960, doi:10.1002/jgt.20597, S2CID 754481.
  6. Royle, G. F028A data
  7. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  8. E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189-202, 2003
  9. Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2015-09-12 at the Wayback Machine
  • Coxeter, H. S. M. "My Graph." Proc. London Math. Soc. 46, 117-136, 1983.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.