graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

the term Heawood family refers to either one of the following two related graph families generated via ΔY- and YΔ-transformations: * the family of 20 graphs generated from the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

K_7

. * the family of 78 graphs generated from

K_7

and

K_

. In either setting the members of the graph family are collectively known as Heawood graphs, as the

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. Combinatorial properties The graph is cubic, and all cycles in the graph have six or more edges. ...

is a member. This is in analogy to the Petersen family, which too is named after its member the

Petersen graph 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 i ...

. The Heawood families are significant in

topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

. They contain the smallest known examples of intrinsically knotted graphs, of graphs that are not 4-flat, and of graphs with

Colin de Verdière graph invariant Colin de Verdière's invariant is a graph parameter \mu(G) for any Graph (discrete mathematics), graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certa ...

\mu=6

The $K_7$ -family

The

K_7

-family is generated from the

K_7

through repeated application of ΔY- and YΔ-transformations. The family consists of 20 graphs, all of which have 21 edges. The unique smallest member,

K_7

, has seven vertices. The unique largest member, the

, has 14 vertices. Only 14 out of the 20 graphs are intrinsically knotted, all of which are minor minimal with this property. The other six graphs have knotless embeddings. This shows that knotless graphs are not closed under ΔY- and YΔ-transformations. All members of the

K_7

-family are intrinsically chiral.

The $K_$ -family

The

K_

-family is generated from the

complete multipartite graph In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge h ...

K_

through repeated application of ΔY- and YΔ-transformations. The family consists of 58 graphs, all of which have 22 edges. The unique smallest member,

K_

, has eight vertices. The unique largest member has 14 vertices. All graphs in this family are intrinsically knotted and are minor minimal with this property.

The $\$ -family

The Heawood family generated from both

K_7

and

K_

through repeated application of ΔY- and YΔ-transformations is the disjoint union of the

K_7

-family and the

K_

-family. It consists of 78 graphs. This graph family has significance in the study of 4-flat graphs, i.e., graphs with the property that every 2-dimensional

CW complex In mathematics, and specifically in topology, a CW complex (also cellular complex or cell complex) is a topological space that is built by gluing together topological balls (so-called ''cells'') of different dimensions in specific ways. It generali ...

built on them can be embedded into 4-space. Hein van der Holst (2006) showed that the graphs in the Heawood family are not 4-flat and have

\mu = 6

. In particular, they are neither planar nor linkless. Van der Holst suggested that they might form the complete list of excluded minors for both the 4-flat graphs and the graphs with

\mu\le 5

. This conjecture can be further motivated from structural similarities to other topologically defined graphs classes: *

K_5

and

K_

(the Kuratowski graphs) are the excluded minors for

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s and

\mu\le 3

. *

K_6

and

K_

generate all excluded minors for linkless graphs and

\mu\le 4

(the Petersen family). *

K_7

and

K_{3,3,1,1}

are conjectured to generate all excluded minors for 4-flat graphs and

\mu\le 5

(the ''Heawood family'').

References

Mellor, B., & Wilson, R. (2023)
Topological Symmetries of the Heawood family
arXiv preprint arXiv:2311.08573. Goldberg, N., Mattman, T. W., & Naimi, R. (2014). Many, many more intrinsically knotted graphs. Algebraic & Geometric Topology, 14(3), 1801-1823. van der Holst, H. (2006)
Graphs and obstructions in four dimensions
Journal of Combinatorial Theory, Series B, 96(3), 388-404. Graph families

The K_7-family

The K_-family

The \-family

References

The $K_7$ -family

The $K_$ -family

The $\$ -family