Heawood graph
Heawood graph | |
---|---|
Table of graphs and parameters |
In the
Combinatorial properties
The graph is
There are 24
There are 28 six-vertex cycles in the Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the Coxeter graph.[4]
Geometric and topological properties
The Heawood graph is a
The map can be faithfully realized as the Szilassi polyhedron,[8] the only known polyhedron apart from the tetrahedron such that every pair of faces is adjacent.
The Heawood graph is the
The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number (sequence A110507 in the OEIS). Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.
The Heawood graph is the smallest cubic graph with Colin de Verdière graph invariant μ = 6.[9]
The Heawood graph is a unit distance graph: it can be embedded in the plane such that adjacent vertices are exactly at distance one apart, with no two vertices embedded to the same point and no vertex embedded into a point within an edge.[10]
Algebraic properties
The automorphism group of the Heawood graph is isomorphic to the projective linear group PGL2(7), a group of order 336.[11] It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Heawood graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. More strongly, the Heawood graph is 4-arc-transitive.[12] According to the
It has
The characteristic polynomial of the Heawood graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Gallery
-
chromatic index3
-
chromatic number2
-
embedded in a torus (shown as a square)
-
embedded in a torus (compare video)
References
- ^ Weisstein, Eric W. "Heawood Graph". MathWorld.
- ^ a b Brouwer, Andries E. "Heawood graph". Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)
- MR 2099150.
- S2CID 754481.
- ^
- JSTOR 3219140. Archived from the original(PDF) on 2012-02-05. Retrieved 2006-10-27.
- ^ Heawood, P. J. (1890). "Map-colour theorem". Quarterly Journal of Mathematics. First Series. 24: 322–339.
- ^ Szilassi, Lajos (1986), "Regular toroids" (PDF), Structural Topology, 13: 69–80
- .
- Bibcode:2009arXiv0912.5395G.
- ISBN 0-444-19451-7. Archived from the originalon 2010-04-13. Retrieved 2019-12-18.
- ^ Conder, Marston; Morton, Margaret (1995). "Classification of Trivalent Symmetric Graphs of Small Order" (PDF). Australasian Journal of Combinatorics. 11: 146.
- ^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2008-07-20 at the Wayback Machine
- ^ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- ^ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018