TOPICS
Search

Petersen Family Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Petersen family of graphs, not to be confused with generalized Petersen graphs, are a set of seven graphs obtained from the Petersen graph (or complete graph K_6) by del -Y or Y-del transforms.

NablaYTransforms

Here, the del -Y transform corresponds to replacing the three graph edges forming a triangle graph C_3 are by three graph edges and a new graph vertex that form a Y, and the del -Y transform to the reverse operation of this.

PetersenFamilyGraphs
PetersenGraphs

As illustrated above and enumerated in the following table, the Petersen family graphs include the Petersen graph P, complete tripartite graph K_(1,3,3), complete graph K_6, and complete bipartite graph minus edge K_(4,4)-e.

indexvertex countgraph
110Petersen graph P
29Petersen family graph P_2
38Petersen family graph P_3
47Petersen family graph P_4
57complete tripartite graph K_(1,3,3)
66complete graph K_6
78complete bipartite graph minus edge K_(4,4)-e

Sachs (1983) showed that the seven graphs of the Petersen family are intrinsically linked, i.e., no matter how they are embedded in space, they have cycles that are linked to each other. He also suggested characterization of these graphs via forbidden subgraphs. Robertson et al. (1993) resolved this question by establishing that intrinsically linked graphs are characterized by having a member of the Petersen family as a graph minor.

In addition, the Petersen family graphs are among the forbidden minors of apex graphs.

See also

Apex Graph, Forbidden Minor, Generalized Petersen Graph, Intrinsically Linked Graph, Linklessly Embeddable Graph, Petersen Graph, Robertson's Apex Graph

Explore with Wolfram|Alpha

References

Adams, C. C. The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots. New York: W. H. Freeman, pp. 221-222, 1994.Robertson, N.; Seymour, P. D.; and Thomas, R. "'Linkless Embeddings of Graphs in 3-Space." Bull. Amer. Math. Soc. 28, 84-89, 1993.Sachs, H. "On a Spatial Analogue of Kuratowski's Theorem on Planar Graphs--An Open Problem". In Graph Theory: Proceedings of a Conference held in Łagòw, Poland, February 10-13, 1981 (Ed. M. Horowiecki, J. W. Kennedy, and M. M. Sysło). New York: Springer-Verlag, pp. 230-241, 1983.

Cite this as:

Weisstein, Eric W. "Petersen Family Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PetersenFamilyGraphs.html

Subject classifications