User:MWinter4/Heawood family
This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. The current/final version of this article may be located at Heawood family now or in the future. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
In graph theory the name Heawood family is used to refer to two related graph families that are closed under ΔY- and YΔ-transformations:
- the family of 20 graphs generated from the complete graph .
- the family of 78 graphs generated from and .
The members of either Heawood family are sometimes called Heawood graphs, though this has the potential for confusion with the Heawood graph. The Heawood graph is a however a members of both families. This is in analogy to the Petersen family, which too is named after a notable member – the Petersen graph.
The Heawood families play a major role in topological graph theory. No member of either family is 4-flat, and no members of the -family is knotless.
No member of the Heawood family is 4-flat, and therefore neither linkless nor planar. All members have Colin de Verdière invariant . It is conjectured that the family of Heawood graphs is the complete list of excluded minors for both the 4-flat graphs and the graphs with .
It is known that neither the Heawood family nor the -family gives the complete list of excluded minors for the knotless graphs.
The -family
[edit]The -family plays an important role in the study of knotless graphs. All members of the family are excluded minors for the class of knotless graphs, but they are not a complete list.
The -family
[edit]The Heawood family plays an important role in the study of 4-flat graphs. The Heawood graphs are the only excluded minors for the 4-flat graphs.
Background
[edit]The Heawood family naturally generalize the excluded minors for planar and linkless graphs. For all of those the list of excluded minors is closed under ΔY- and YΔ-transformations. The generators are:
- for planar, and (the Kuratowski graphs).
- for linkless, and (generate the Petersen family).
- (conjecturally) for 4-flat, and (generate the Heawood family).
For planar and linkless graphs it is actually sufficient to generate the excluded minors from only and respectively. For the Heawood family however both generators are necessary. The family generated by has 20 members and the family generated by has 58 members. The union of these disjoint families yields the Heawood family.
References
[edit]