Heawood 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 .
- the family of 78 graphs generated from and .
In either setting the members of the graph family are collectively known as Heawood graphs, as 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,[1] that are not 4-flat, or that have Colin de Verdière graph invariant .[2]
The -family
[edit]The -family is generated from the complete graph through repeated application of ΔY- and YΔ-transformations. The family consists of 20 graphs, all of which have 21 edges. The unique smallest member, , has seven vertices. The unique largest member, the Heawood graph, has 14 vertices.[1]
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.[1] This shows that knotless graphs are not closed under ΔY- and YΔ-transformations.
All members of the -family are intrinsically chiral.[3]
The -family
[edit]The -family is generated from the complete multipartite graph through repeated application of ΔY- and YΔ-transformations. The family consists of 58 graphs, all of which have 22 edges. The unique smallest member, , has eight vertices. The unique largest member has 14 vertices.[1]
All graphs in this family are intrinsically knotted and are minor minimal with this property.[1]
The -family
[edit]The Heawood family generated from both and through repeated application of ΔY- and YΔ-transformations is the disjoint union of the -family and the -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 . 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 .[2]
This conjecture can be further motivated from structural similarities to other topologically defined graphs classes:
- and (the Kuratowski graphs) are the excluded minors for planar graphs and .
- and generate all excluded minors for linkless graphs and (the Petersen family).
- and are conjectured to generate all excluded minors for 4-flat graphs and (the Heawood family).
References
[edit]- ^ a b c d e Goldberg, N., Mattman, T. W., & Naimi, R. (2014). Many, many more intrinsically knotted graphs. Algebraic & Geometric Topology, 14(3), 1801-1823.
- ^ a b van der Holst, H. (2006). Graphs and obstructions in four dimensions. Journal of Combinatorial Theory, Series B, 96(3), 388-404.
- ^ Mellor, B., & Wilson, R. (2023). Topological Symmetries of the Heawood family. arXiv preprint arXiv:2311.08573.