Petersen family

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K_6. 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. 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 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 K_6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph K_4,4, and the seven-vertex complete tripartite graph K_3,3,1.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related concepts (9)

Networks are everywhere and we are confronted with many networks in our daily life. Networks such as Internet, World Wide Web, social, biological and economical networks have been subject to extensive studies in the last decade. The volume of publications ...

EPFL2011

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 more than one apex; for example, in the minimal nonplanar graphs K_5 or K_3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

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 is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.

Forbidden graph characterization

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 forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.