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

Heawood graph
Heawood Graph
Named afterPercy John Heawood
Vertices14
Edges21
Radius3
Diameter3
Girth6
Automorphisms336 (PGL2(7))
Chromatic number2
Chromatic index3
Genus1
Book thickness3
Queue number2
PropertiesBipartite
Cubic
Cage
Distance-transitive
Distance-regular
Toroidal
Hamiltonian
Symmetric
Orientably simple
Table of graphs and parameters

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

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.

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

The Heawood graph is the Levi graph of the Fano plane, 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 Bruhat-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 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.[7]

Algebraic properties

The automorphism group of the Heawood graph is isomorphic to the projective linear group PGL2(7), a group of order 336.[8] 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.[9] According to the Foster census, the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices.[10][11]

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

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

3-crossing Heawood graph

The Heawood graph has crossing number 3.

Heawood graph 3color edge

The chromatic index of the Heawood graph is 3.

Heawood graph 2COL

The chromatic number of the Heawood graph is 2.

7x-torus

An embedding of the Heawood graph into a torus (shown as a square with periodic boundary conditions) partitioning it into seven mutually-adjacent regions

References

  1. ^ Weisstein, Eric W. "Heawood Graph". MathWorld.
  2. ^ a b Brouwer, Andries E. "Heawood graph". Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989). External link in |work= (help)
  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, arXiv:1002.1960, doi:10.1002/jgt.20597.
  5. ^ Brown, Ezra (2002). "The many names of (7,3,1)" (PDF). Mathematics Magazine. 75 (2): 83–94. doi:10.2307/3219140. JSTOR 3219140.
  6. ^ Heawood, P. J. (1890). "Map colouring theorems". Quarterly J. Math. Oxford Ser. 24: 322–339.
  7. ^ Gerbracht, Eberhard H.-A. (2009). "Eleven unit distance embeddings of the Heawood graph". arXiv:0912.5395. Bibcode:2009arXiv0912.5395G..
  8. ^ 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.
  9. ^ Conder and Morton (1995). "Classification of Trivalent Symmetric Graphs of Small Order". Australasian Journal of Combinatorics. 11: 146.
  10. ^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2008-07-20 at the Wayback Machine
  11. ^ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  12. ^ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Bitangents of a quartic

In the theory of algebraic plane curves, a general quartic plane curve has 28 bitangent lines, lines that are tangent to the curve in two places. These lines exist in the complex projective plane, but it is possible to define quartic curves for which all 28 of these lines have real numbers as their coordinates and therefore belong to the Euclidean plane.

An explicit quartic with twenty-eight real bitangents was first given by Plücker (1839) As Plücker showed, the number of real bitangents of any quartic must be 28, 16, or a number less than 9. Another quartic with 28 real bitangents can be formed by the locus of centers of ellipses with fixed axis lengths, tangent to two non-parallel lines.Shioda (1995) gave a different construction of a quartic with twenty-eight bitangents, formed by projecting a cubic surface; twenty-seven of the bitangents to Shioda's curve are real while the twenty-eighth is the line at infinity in the projective plane.

Coxeter graph

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 graphs are known. The Coxeter graph is one of the 13 such graphs. It is named after Harold Scott MacDonald Coxeter.

Crossing number (graph theory)

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown

that drawing graphs with few crossings makes it easier for people to understand the drawing.The study of crossing numbers originated in Turán's brick factory problem, in which Pál Turán asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a complete bipartite graph, The same problem arose independently in sociology at approximately the same time, in connection with the construction of sociograms. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the complete graphs.

The crossing number inequality states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2. It has applications in VLSI design and incidence geometry.

Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the rectilinear crossing number, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position. The problem of determining this number is closely related to the happy ending problem.

Dejter graph

In the mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices, 336 edges and girth 4. The Dejter graph is

obtained by deleting a copy

of the Hamming code of length 7 from the binary

7-cube.

The Dejter graph, and by extension any graph obtained by deleting a Hamming code of length 2r-1 from a

(2r-1)-cube, is a symmetric graph (and so it is both vertex-transitive and edge-transitive but is not half-transitive).

In particular, the Dejter graph admits a 3-factorization into two

copies of the Ljubljana graph, which is the third smallest existing edge- but not vertex-transitive graph of regular degree 3, also called a semi-symmetric cubic graph.

In fact, it is proven that the Dejter graph can be 2-colored, say in the color set {red, blue}, as in the top figure to the right, so that both the resulting edge-monochromatic red and blue vertex-spanning subgraphs are copies of the Ljubljana graph. These two copies contain exactly the 112 vertices of the Dejter graph and 168 edges each, having both copies girth 10, while the Dejter graph has girth 6 and the 7-cube girth 4. It seems that the Dejter graph is the smallest symmetric graph having a connected self-complementary vertex-spanning semi-symmetric cubic subgraph.

Both the red and blue vertex-spanning Ljubljana subgraphs of the drawn Dejter graph can be presented as covering graphs of the Heawood graph, namely as 8-covers of the Heawood graph. This is suggested in each of the two representations of the Ljubljana graph, (red above, blue below, both to the right), by alternately coloring the inverse images of successive vertices of the Heawood graph, say in black and white (better viewed by twice clicking on images for figure enlargements), according to the Heawood graph bipartition. Each such inverse image is formed by the 8 neighbors, along a fixed coordinate direction of the 7-cube, of the half of the Hamming code having a fixed weight, 0 or 1. By exchanging these weights via the permutation (0 1), one can pass from the adjacency offered by the red Ljubljana graph to the one offered by the blue Ljubljana graph, or vice versa.

One seventh of the Dejter graph appears in a separate figure down below that can be obtained from the two resulting copies of the Heawood graph.

Distance-regular graph

In mathematics, 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 i = d(v, w).

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.

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. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2.

Fano plane

In finite geometry, the Fano plane (after Gino Fano) is the finite projective plane of order 2. It is the finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. The standard notation for this plane, as a member of a family of projective spaces, is PG(2,2) where PG stands for "Projective Geometry", the first parameter is the geometric dimension and the second parameter is the order.

The Fano plane is an example of a finite incidence structure, so many of its properties can be established using combinatorical techniques and other tools used in the study of incidence geometries. Since it is a projective space, algebraic techniques can also be effective tools in its study.

Gallery of named graphs

Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

Girth (graph theory)

In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity.

For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

Heawood

Heawood is a surname. Notable people with the surname include:

Jonathan Heawood, British journalist

Percy John Heawood (1861–1955), British mathematicianHeawood conjecture

Heawood graph

Heawood number

Hoffman–Singleton graph

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.

Incidence structure

In mathematics, an abstract system consisting of two types of objects and a single relationship between these types of objects is called an incidence structure. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

Incidence structures are most often considered in the geometrical context where they are abstracted from, and hence generalize, planes (such as affine, projective, and Möbius planes), but the concept is very broad and not limited to geometric settings. Even in a geometric setting, incidence structures are not limited to just points and lines; higher-dimensional objects (planes, solids, n-spaces, conics, etc.) can be used. The study of finite structures is sometimes called finite geometry.

Levi graph

In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for F. W. Levi, who wrote about them in 1942.The Levi graph of a system of points and lines usually has girth at least six: Any 4-cycles would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure. Levi graphs of configurations are biregular, and every biregular graph with girth at least six can be viewed as the Levi graph of an abstract configuration.Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in Euclidean space. For every Levi graph, there is an equivalent hypergraph, and vice versa.

Ljubljana graph

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there are exactly 168 cycles of length 10 in it. There are also 168 cycles of length 12.

Mathematics and fiber arts

Ideas from Mathematics have been used as inspiration for fiber arts including quilt making, knitting, cross-stitch, crochet, embroidery and weaving. A wide range of mathematical concepts have been used as inspiration including topology, graph theory, number theory and algebra. Some techniques such as counted-thread embroidery are naturally geometrical; other kinds of textile provide a ready means for the colorful physical expression of mathematical concepts.

Szilassi polyhedron

The Szilassi polyhedron is a nonconvex polyhedron, topologically a torus, with seven hexagonal faces.

Toroidal graph

In mathematics, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.

Unit distance graph

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. Edges of unit distance graphs sometimes cross each other, so they are not always planar; a unit distance graph without crossings is called a matchstick graph.

The Hadwiger–Nelson problem concerns the chromatic number of unit distance graphs. It is known that there exist unit distance graphs requiring five colors in any proper coloring, and that all such graphs can be colored with at most seven colors. Another important open problem concerning unit distance graphs asks how many edges they can have relative to their number of vertices.

Vertex-transitive graph

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism

such that

In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.

Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph).

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.