YΔ- and ΔY-transformation

Let G be a graph (potentially a multigraph). Suppose G contains a triangle \Delta with vertices x_1,x_2,x_3 and edges e_{12},e_{23},e_{31}. A ΔY-transformation of G at \Delta deletes the edges e_{12},e_{23},e_{31} and adds a new vertex y adjacent to each of x_1,x_2,x_3. Conversely, if y is a vertex of degree three with neighbors x_1,x_2,x_3, then a YΔ-transformation of G at y deletes y and adds three new edges e_{12},e_{23},e_{31}, where e_{ij} connects x_i and x_j. If the resulting graph should be a simple graph, then any resulting parallel edges are to be replaced by a single edge. == Relevance ==

ΔY- and YΔ-transformations are a tool both in pure graph theory as well as applications. Both operations preserve a number of natural topological properties of graphs. For example, applying a YΔ-transformation to a 3-vertex of a planar graph, or a ΔY-transformation to a triangular face of a planar graph, results again in a planar graph. This was used in the original proof of Steinitz's theorem, showing that every 3-connected planar graph is the edge graph of a polyhedron. Applying ΔY- and YΔ-transformations to a linkless graph results again in a linkless graph. In this context they are also known as star-triangle transformations and are a special case of star-mesh transformations. == ΔY-families ==

The ΔY-family generated by a graph G is the smallest family of graphs that contains G and is closed under YΔ- and ΔY-transformations. Equivalently, it is constructed from G by recursively applying these transformations until no new graph is generated. If G is a finite graph it generates a finite ΔY-family, all members of which have the same edge count. The ΔY-family generated by several graphs is the smallest family that contains all these graphs and is closed under YΔ- and ΔY-transformation. Some notable families are generated in this way: • the Petersen family is generated from the complete graph K_6. It consists of the seven forbidden minors for the class of linkless graphs. • the Heawood family is generated from K_7 and K_{3,3,1,1}. It consists of 78 graphs, each of which is a forbidden minors for the class of 4-flat graphs. == YΔY-reducible graphs ==

is linkless but not YΔY-reducible. A graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of ΔY- or YΔ-transformations and the following normalization steps: • removing a loop, • removing a parallel edge, • removing a vertex of degree one, • smoothing out a vertex of degree two, i.e., replacing it by a single edge between its two former neighbors. The YΔY-reducible graphs form a minor closed family and therefore have a forbidden minor characterization (by the Robertson–Seymour theorem). The graphs of the Petersen family constitute some (but not all) of the excluded minors. In fact, already more than 68 billion excluded minor are known. The class of YΔY-reducible graphs lies between the classes of planar graphs and linkless graphs: each planar graph is YΔY-reducible, while each YΔY-reducible graph is linkless. Both inclusions are strict: K_5 is not planar but YΔY-reducible, while the graph in the figure is not YΔY-reducible but linkless. == References ==