Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Coxeter graph
Summary
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.
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.
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 .
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 .) This construction exhibits the Coxeter graph as an induced subgraph of 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.
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.
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 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.
The Coxeter graph is also uniquely determined by its graph spectrum, the set of graph eigenvalues of its adjacency matrix.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (2)
MATH-360: Graph theory
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
MATH-335: Coxeter groups
Study groups generated by reflections
Related lectures (10)
Coxeter Groups: Reflections and Fundamental Regions
Explores Coxeter groups, reflections, fundamental regions, and classification by Coxeter graphs.
McKay Graphs of Finite Subgroups of SU(2)
Explores McKay graphs for finite subgroups of SU(2) and the corresponding Coxeter graphs.
Positive Definite Coxeter Graphs
Explores the classification of positive definite connected Coxeter graphs through detailed calculations and proofs.
Related publications (4)
Related concepts (7)
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood. The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6. It is a distance-transitive graph (see the Foster census) and therefore distance regular. There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle.
Distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith. A distance-transitive graph is interesting partly because it has a large automorphism group.
Distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w. Some authors exclude the complete graphs and disconnected graphs from this definition. Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.