Heawood graph

Heawood graph

infobox graph
name = Heawood graph


image_caption =
namesake = Percy John Heawood
vertices = 14
edges = 21
girth = 6
chromatic_number = 2
chromatic_index = 3
properties = Cubic Cage Distance-regular Toroidal

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges. 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 also the Levi graph of the Fano plane, the graph representing incidences between points and lines in that geometry. It is a distance-regular graph; its group of symmetries is PGL2(7) (Brouwer).

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 (Brouwer).

The Heawood graph is named after Percy John Heawood, who in 1890 proved that every subdivision of the torus into polygons can be colored by at most seven colors. The Heawood graph forms a subdivision of the torus with seven mutually-adjacent regions, showing that this bound is tight.

The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number OEIS|id=A110507.

Torus embedding

The Heawood graph is a toroidal graph; that is, it can be embedded without crossings onto a torus. One embedding of this type places its vertices and edges into three-dimensional Euclidean space as the set of vertices and edges of a nonconvex polyhedron with the topology of a torus, the Szilassi polyhedron.

References

*

*

External links

*

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Heawood conjecture — The Heawood conjecture or Ringel–Youngs theorem in graph theory gives an upper bound for the number of colors which are sufficient for graph coloring on a surface of a given genus. It was proven in 1968 by Gerhard Ringel and J. W. T. Youngs. One… …   Wikipedia

  • Heawood — Percy John Heawood (* 8. September 1861 in Newport, Shropshire; † 24. Januar 1955 in Durham) war ein britischer Mathematiker. Leben und Wirken Heawood studierte ab 1880 am Exeter College in Oxford u.a. bei Henry John Stephen Smith. Während des… …   Deutsch Wikipedia

  • Heawood number — In mathematics, the Heawood number of a surface is a certain upper bound for the maximal number of colors needed to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the sphere that no more than:… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • 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 …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • Graphe de Heawood — Représentation du graphe de Heawood. Nombre de sommets 14 Nombre d arêtes 21 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Toroidal graph — [ A graph (similar to the Heawood graph) embedded on the torus such that no edges cross. ] In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph s vertices can be placed on a torus such that no edges… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Einheitsdistanz-Graph — Der Petersen Graph ist ein Einheitsdistanz Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist. Ein Einheitsdistanz Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz Graphen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”