HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Petersen family is a set of seven
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
s that includes the
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 n ...
and the
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. A complete digraph is a directed graph in which every pair of distinct vertices is ...
. The Petersen family is named after Danish mathematician
Julius Petersen Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 5 August 1910, Copenhagen) was a Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory. Biography Petersen's interest ...
, 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 minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
s 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.


Definition

The form of Δ-Y and Y-Δ transforms used to define the Petersen family is as follows: *If a graph contains a vertex with exactly three neighbors, then the Y-Δ transform of at is the graph formed by removing from and adding edges between each pair of its three neighbors. *If a graph contains a triangle , then the Δ-Y transform of at is the graph formed by removing edges , , and from and adding a new vertex connected to all three of , , and . 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 In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
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 by combinations of Δ-Y and Y-Δ transforms. The Petersen family then consists of every graph that can be reached from the
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 n ...
by a combination of Δ-Y and Y-Δ transforms. There are seven graphs in the family, including the
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. A complete digraph is a directed graph in which every pair of distinct vertices is ...
on six vertices, the eight-vertex graph formed by removing a single edge from the
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..Electronic edition page 17. Graph theory i ...
, and the seven-vertex complete tripartite graph .


Forbidden minors

A minor of a graph ''G'' is another graph formed from ''G'' by contracting and removing edges. As the
Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...
shows, many important families of graphs can be characterized by a finite set of
forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
s: for instance, according to
Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on five ...
, the
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. In other words, it can be drawn in such a way that no edges cro ...
s are exactly the graphs that have neither the
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. A complete digraph is a directed graph in which every pair of distinct vertices is ...
''K''5 nor the
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..Electronic edition page 17. Graph theory i ...
''K''3,3 as minors.
Neil Robertson Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...
, Paul Seymour, and
Robin Thomas Robin may refer to: Animals * Australasian robins, red-breasted songbirds of the family Petroicidae * Many members of the subfamily Saxicolinae (Old World chats), including: **European robin (''Erithacus rubecula'') **Bush-robin ** Forest r ...
used the Petersen family as part of a similar characterization of
linkless embedding In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding ...
s of graphs, embeddings of a given graph into
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
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..
Horst Sachs Horst Sachs (27 March 1927 – 25 April 2016) was a German mathematician, an expert in graph theory, a recipient of the Euler Medal (2000). He earned the degree of Doctor of Science (Dr. rer. nat.) from the Martin-Luther-Universität Halle-Witt ...
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 ''K''4 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 A claw is a curved, pointed appendage found at the end of a toe or finger in most amniotes (mammals, reptiles, birds). Some invertebrates such as beetles and spiders have somewhat similar fine, hooked structures at the end of the leg or tarsus ...
''K''1,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 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. It is ''an'' apex, not ''the'' apex because an apex graph may have ...
(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..


References

{{reflist Graph families Graph minor theory