Petersen family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.
Any of the graphs in the Petersen family can be transformed into any other graph in the family by YΔ- and ΔY-transformations, operations in which a triangle is replaced by a degree-three vertex or vice versa. These seven graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked.[1] They are also among the forbidden minors for the YΔY-reducible graphs.[2][3]
Definition
[edit]The form of YΔ- and ΔY-transformations used to define the Petersen family is as follows:
- If a graph G contains a vertex v with exactly three neighbors, then the YΔ-transform of G at v is the graph formed by removing v from G and adding edges between each pair of its three neighbors.
- If a graph H contains a triangle uvw, then the ΔY-transform of H at uvw is the graph formed by removing edges uv, vw, and uw from H and adding a new vertex connected to all three of u, v, and w.
These transformations are so called because of the Δ shape of a triangle in a graph and the Y shape of a degree-three vertex. Although these operations can in principle lead to multigraphs, that does not happen within the Petersen family. Because these operations preserve the number of edges in a graph, there are only finitely many graphs or multigraphs that can be formed from a single starting graph G by combinations of ΔY- and YΔ-transforms.
The Petersen family then consists of every graph that can be reached from the Petersen graph by a combination of ΔY- and YΔ-transforms. There are seven graphs in the family, including the complete graph K6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph K4,4, and the seven-vertex complete tripartite graph K3,3,1.
Forbidden minors
[edit]
A minor of a graph G is another graph formed from G by contracting and removing edges. As the Robertson–Seymour theorem shows, many important families of graphs can be characterized by a finite set of forbidden minors: for instance, according to Wagner's theorem, the planar graphs are exactly the graphs that have neither the complete graph K5 nor the complete bipartite graph K3,3 as minors.
Neil Robertson, Paul Seymour, and Robin Thomas used the Petersen family as part of a similar characterization of linkless embeddings of graphs, embeddings of a given graph into Euclidean space in such a way that every cycle in the graph is the boundary of a disk that is not crossed by any other part of the graph.[1] Horst Sachs had previously studied such embeddings, shown that the seven graphs of the Petersen family do not have such embeddings, and posed the question of characterizing the linklessly embeddable graphs by forbidden subgraphs.[4] Robertson et al. solved Sachs' question by showing that the linkless embeddable graphs are exactly the graphs that do not have a member of the Petersen family as a minor.
The Petersen family also form some of the forbidden minors for another family of graphs, the YΔY-reducible graphs. A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a ΔY- or YΔ-transform, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge. For instance, the complete graph K4 can be reduced to a single vertex by a YΔ-transform that turns it into a triangle with doubled edges, removal of the three doubled edges, a ΔY-transform that turns it into the claw K1,3, and removal of the three degree-one vertices of the claw. Each of the Petersen family graphs forms a minimal forbidden minor for the family of YΔY-reducible graphs.[2] However, Neil Robertson provided an example of an apex graph (a linkless embeddable graph formed by adding one vertex to a planar graph) that is not YΔY-reducible, showing that the YΔY-reducible graphs form a proper subclass of the linkless embeddable graphs and have additional forbidden minors.[2] In fact, as Yaming Yu showed, there are at least 68,897,913,652 forbidden minors for the YΔY-reducible graphs beyond the seven of the Petersen family.[3]
References
[edit]- ^ a b Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
- ^ a b c Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, pp. 100–101.
- ^ a b Yu, Yaming (2006), "More forbidden minors for wye-delta-wye reducibility" (PDF), Electronic Journal of Combinatorics, 13 (1): #R7, doi:10.37236/1033.
- ^ Sachs, Horst (1983), "On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem", in Horowiecki, M.; Kennedy, J. W.; Sysło, M. M. (eds.), Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 230–241, doi:10.1007/BFb0071633, ISBN 978-3-540-12687-4.