Coxeter graph
Encyclopedia
In the mathematical
field of graph theory
, the Coxeter graph is a 3-regular graph
with 28 vertices and 42 edges. All the cubic
distance-regular graph
s are known. The Coxeter graph is one of the 13 such graphs.
It 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
.
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 currently known, but an 11-crossing, 26-vertex graph may exist .
. 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.
The Coxeter graph is also uniquely determined by the its graph spectrum, the set of graph eigenvalues of its adjacency matrix
.
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.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Coxeter graph is a 3-regular graph
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
with 28 vertices and 42 edges. All the cubic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
distance-regular graph
Distance-regular graph
In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...
s are known. The Coxeter graph is one of the 13 such graphs.
It has chromatic number 3, chromatic index 3, radius 4, diameter 4 and girth 7. It is also a 3-vertex-connected graph
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
and a 3-edge-connected graph
K-edge-connected graph
In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
.
The Coxeter graph is hypohamiltonian
Hypohamiltonian graph
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.-History:...
: 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
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
11, and is the smallest cubic graph with that crossing number currently known, but an 11-crossing, 26-vertex graph may exist .
Algebraic properties
The automorphism group of the Coxeter graph is a group of order 336. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Coxeter graph is a symmetric graphSymmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
. 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.
The Coxeter graph is also uniquely determined by the its graph spectrum, the set of graph eigenvalues of its adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
.
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
Lovász conjecture
In graph theory, the Lovász conjecture is a classical problem on Hamiltonian paths in graphs. It says:The original article of Lovász stated the result in the opposite, butthis version became standard...
, 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
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K2, the Petersen graph
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
, the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.
The characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of the Coxeter graph is
. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.