Coxeter graph

In the field of graph theory, mathematicians study structures made of points and lines. One highly unique structure is the Coxeter graph. It is a 3-regular graph, which means every single vertex has exactly three edges connected to it. This specific graph contains 28 vertices and 42 edges. It is also classified as one of the 13 known cubic distance-regular graphs.

This classification means the distances between its vertices follow a very strict and predictable pattern.

The Coxeter graph possesses several complex mathematical properties. It has a chromatic number of 3 and a chromatic index of 3. This means you can color the vertices so that no two connected vertices share a color using only three colors.

Its girth is 7, which is the length of its shortest cycle. The graph also has a radius of 4 and a diameter of 4. It is both 3-vertex-connected and 3-edge-connected. This high level of connectivity makes the structure very robust.

Additionally, it is a 1-planar graph, meaning it can be drawn such that each edge is crossed at most once.

One of the most famous traits of this graph is that it is hypohamiltonian. In graph theory, a Hamiltonian cycle is a path that visits every vertex exactly once before returning to the start. The Coxeter graph does not contain such a cycle. However, if you remove any single vertex from the graph, the remaining structure becomes Hamiltonian.

This makes it a famous counterexample to certain versions of the Lovász conjecture. While it lacks a full cycle, it does contain a Hamiltonian path. It is one of only five known vertex-transitive graphs that lack Hamiltonian cycles.

There are several distinct ways to construct this mathematical object. The simplest method uses a Fano plane. First, you take the 35 possible 3-combinations of 7 objects. You then discard the 7 triplets that form the lines of the Fano plane. This leaves 28 triplets to serve as vertices. You connect two triplets if they are disjoint.

You can also build it from the Heawood graph. In this version, you create a vertex for every 6-cycle in the Heawood graph. You then connect vertices if their corresponding 6-cycles are disjoint.

Another construction method involves the Hoffman-Singleton graph. To do this, you select any vertex, which we can call vertex v, within the Hoffman-Singleton graph. You then identify an independent set of size 15 that includes vertex v. By deleting the 7 neighbors of vertex v along with the entire independent set, you are left with the Coxeter graph.

This shows how complex graphs can be nested within even larger mathematical structures.

The Coxeter graph is named after the mathematician Harold Scott MacDonald Coxeter. It is a highly symmetric object with an automorphism group of order 336. This group acts transitively on the vertices, edges, and arcs. Because of this, it is considered a symmetric graph. In the Foster census, it is identified as F28A. It holds the unique distinction of being the only cubic symmetric graph with exactly 28 vertices.

Algebraically, the graph is also uniquely identified by its spectrum. The spectrum is the set of eigenvalues from its adjacency matrix. The characteristic polynomial of the Coxeter graph is a specific mathematical expression. This polynomial is unique to this graph, meaning no other graph shares this exact spectrum. This allows mathematicians to recognize the Coxeter graph purely through its algebraic properties. It also has a rectilinear crossing number of 11. This makes it the smallest cubic graph to possess that specific crossing number.