Heawood graph

Last updated
Heawood graph
Heawood Graph.svg
Named after Percy John Heawood
Vertices 14
Edges 21
Radius 3
Diameter 3
Girth 6
Automorphisms 336 (PGL2(7))
Chromatic number 2
Chromatic index 3
Genus 1
Book thickness 3
Queue number 2
Properties Bipartite
Cubic
Cage
Distance-transitive
Distance-regular
Toroidal
Hamiltonian
Symmetric
Orientably simple
Table of graphs and parameters

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

Contents

Combinatorial properties

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

There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3-color its edges) in eight different ways. [2] Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph. [3]

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

Heawood's map. Opposite edges of the large hexagon are connected to form a torus. Heawood map on a hexagon.svg
Heawood's map. Opposite edges of the large hexagon are connected to form a torus.

The Heawood graph is a toroidal graph; that is, it can be embedded without crossings onto a torus. The result is the regular map {6,3}2,1, with 7 hexagonal faces. [5] Each face of the map is adjacent to every other face, thus as a result coloring the map requires 7 colors. The map and graph were discovered by Percy John Heawood in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal. [6] [7]

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.

Fano plane nimbers.svg
Heawood Levi Fano.svg
Heawood Levi Fano bipartite.svg
Fano plane and two representations of its Levi graph (below as a bipartite graph)

The Heawood graph is the Levi graph of the Fano plane, [5] the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to triangles in the Fano plane. Also, the Heawood graph is the Tits building of the group SL3(F2).

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 Foster census, the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices. [13] [14]

It has book thickness 3 and queue number 2. [15]

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.

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

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 after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

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.

<span class="mw-page-title-main">Symmetric graph</span> Graph in which all ordered pairs of linked nodes are automorphic

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1v1 and u2v2 of G, there is an automorphism

<span class="mw-page-title-main">Gray graph</span>

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

<span class="mw-page-title-main">Hoffman–Singleton graph</span> 7-regular undirected graph with 50 nodes and 175 edges

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

<span class="mw-page-title-main">Coxeter graph</span> Type of graph

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.

<span class="mw-page-title-main">Pappus graph</span> Bipartite, 3-regular undirected graph

In the mathematical field of graph theory, the Pappus graph is a bipartite, 3-regular, undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic, distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.

<span class="mw-page-title-main">Foster graph</span> Bipartite 3-regular graph with 90 vertices and 135 edges

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

<span class="mw-page-title-main">Möbius–Kantor graph</span>

In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

<span class="mw-page-title-main">Shrikhande graph</span> Undirected graph named after S. S. Shrikhande

In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.

<span class="mw-page-title-main">Regular map (graph theory)</span> Symmetric tessellation of a closed surface

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold into topological disks such that every flag can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

<span class="mw-page-title-main">Franklin graph</span> Graph often embedded in the Klein bottle

In the mathematical field of graph theory, the Franklin graph is a 3-regular graph with 12 vertices and 18 edges.

<span class="mw-page-title-main">Folkman graph</span> Bipartite 4-regular graph with 20 nodes and 40 edges

In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

<span class="mw-page-title-main">Dyck graph</span>

In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.

<span class="mw-page-title-main">Nauru graph</span> 24-vertex symmetric bipartite cubic graph

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

<span class="mw-page-title-main">F26A graph</span>

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

<span class="mw-page-title-main">LCF notation</span> Representation of cubic graphs

In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle itself includes two out of the three adjacencies for each vertex, and the LCF notation specifies how far along the cycle each vertex's third neighbor is. A single graph may have multiple different representations in LCF notation.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

<span class="mw-page-title-main">Klein graphs</span>

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

References

  1. Weisstein, Eric W. "Heawood Graph". MathWorld .
  2. 1 2 Brouwer, Andries E. "Heawood graph". Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)
  3. Abreu, M.; Aldred, R. E. L.; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), "Graphs and digraphs with all 2-factors isomorphic", Journal of Combinatorial Theory, Series B , 92 (2): 395–404, doi: 10.1016/j.jctb.2004.09.004 , MR   2099150 .
  4. 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 .
  5. 1 2 Coxeter (1950), "Self-dual configurations and regular graphs" (PDF), Bulletin of the American Mathematical Society, 56, doi:10.1090/S0002-9904-1950-09407-5
  6. Brown, Ezra (2002). "The many names of (7,3,1)" (PDF). Mathematics Magazine . 75 (2): 83–94. doi:10.2307/3219140. JSTOR   3219140. Archived from the original (PDF) on 2012-02-05. Retrieved 2006-10-27.
  7. Heawood, P. J. (1890). "Map-colour theorem". Quarterly Journal of Mathematics. First Series. 24: 322–339.
  8. Szilassi, Lajos (1986), "Regular toroids" (PDF), Structural Topology, 13: 69–80
  9. Hein van der Holst (2006). "Graphs and obstructions in four dimensions" (PDF). Journal of Combinatorial Theory, Series B . 96 (3): 388–404. doi: 10.1016/j.jctb.2005.09.004 .
  10. Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph, arXiv: 0912.5395 , Bibcode:2009arXiv0912.5395G .
  11. Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. New York: North Holland. p.  237. ISBN   0-444-19451-7. Archived from the original on 2010-04-13. Retrieved 2019-12-18.
  12. Conder, Marston; Morton, Margaret (1995). "Classification of Trivalent Symmetric Graphs of Small Order" (PDF). Australasian Journal of Combinatorics. 11: 146.
  13. Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2008-07-20 at the Wayback Machine
  14. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  15. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018