Petersen family
Encyclopedia
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 or Y-Δ transforms, 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
. They are also among the forbidden minors for the YΔY-reducible graphs.
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 multigraph
s, 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.
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 graph
s 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 embedding
s of graphs, embeddings of a given graph into Euclidean space
in such a way that every cycle (graph theory)
in the graph is the boundary of a disk that is not crossed by any other part of the graph. 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. 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. 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. 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Petersen family is a set of seven undirected graphs that includes the Petersen graph
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
and the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K6. The Petersen family is named after Danish mathematician Julius Petersen
Julius Petersen
Julius Peter Christian Petersen was a Danish mathematician.-Biography:Petersen's interests in mathematics were manifold .His famous paper Die Theorie der regulären graphs was a fundamental...
, 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 or Y-Δ transforms, 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
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...
, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked
Link (knot theory)
In mathematics, a link is a collection of knots which do not intersect, but which may be linked together. A knot can be described as a link with one component. Links and knots are studied in a branch of mathematics called knot theory...
. They are also among the forbidden minors for the YΔY-reducible graphs.
Definition
The form of Δ-Y and Y-Δ transforms 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 multigraph
Multigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
s, 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
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
by a combination of Δ-Y and Y-Δ transforms. There are seven graphs in the family, including the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K4,4, and the seven-vertex complete tripartite graph K3,3,1.
Forbidden minors
A minorMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
of a graph G is another graph formed from G by contracting and removing edges. As the Robertson–Seymour theorem
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
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 graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s are exactly the graphs that have neither the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K5 nor the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K3,3 as minors.
Neil Robertson
Neil Robertson (mathematician)
G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
, Paul Seymour, and Robin Thomas
Robin Thomas (mathematician)
Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.Thomas received his doctorate in 1985 from Charles University in Prague, Czechoslovakia , under the supervision of Jaroslav Nešetřil...
used the Petersen family as part of a similar characterization of linkless embedding
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...
s of graphs, embeddings of a given graph into Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
in such a way that every cycle (graph theory)
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in the graph is the boundary of a disk that is not crossed by any other part of the graph. Horst Sachs
Horst Sachs
Horst Sachs is a German mathematician, an expert in graph theory, a recipient of the Euler Medal .He earned the degree of Doctor of Science from the Martin-Luther-Universität Halle-Wittenberg in 1958...
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. 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
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
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. However, Neil Robertson provided an example of an apex graph
Apex graph
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. We say an apex, not the apex because an apex graph may have more than one apex...
(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. 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.