Heawood family

Not to be confused with the Heawood graph, which is a member of the Heawood graph family.

In graph theory 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 $K_{7}$.
• the family of 78 graphs generated from $K_{7}$ and $K_{3,3,1,1}$.

In either setting the members of the graph family are collectively known as Heawood graphs, owing to the fact that the Heawood graph is a member. This is in analogy to the Petersen family, which too is named after its member the Petersen graph.

The Heawood families play a significant role in topological graph theory. They contain the smallest known examples for graphs that are intrinsically knotted, that are not 4-flat, or that have Colin de Verdière graph invariant $\mu =6$.

The $K_{7}$-family

The $K_{7}$-family is generated from the complete graph $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 Heawood graph, 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_{3,3,1,1}$-family

The $K_{3,3,1,1}$-family is generated from the complete multipartite graph $K_{3,3,1,1}$ 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_{3,3,1,1}$, 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 $\{K_{7},K_{3,3,1,1}\}$-family

Unsolved problem in mathematics:

Is the Heawood family the complete list of excluded minors of the 4-flat graphs and for $\mu \leq 5$?

(more unsolved problems in mathematics)

The Heawood family generated from both $K_{7}$ and $K_{3,3,1,1}$ through repeated application of ΔY- and YΔ-transformations is the disjoint union of the $K_{7}$-family and the $K_{3,3,1,1}$-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 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 Colin de Verdière graph invariant $\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 \leq 5$.

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

• $K_{5}$ and $K_{3,3}$ (the Kuratowski graphs) are the excluded minors for planar graphs and $\mu \leq 3$.
• $K_{6}$ and $K_{3,3,1}$ generate all excluded minors for linkless graphs and $\mu \leq 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 \leq 5$ (the Heawood family).