YΔ- and ΔY-transformation
In graph theory, ΔY- and YΔ-transformations (also written delta-wye and wye-delta) are a pair of operations on graphs. A ΔY-transformation replaces a
A YΔ-transformation may create
Formal definition
Let be a graph (potentially a multigraph).
If the edges form a triangle with vertices , then a ΔY-transformation of at removes and adds a new vertex adjacent to all of .
If is a vertex of degree three with neighbors , then a YΔ-transformation of at deletes and adds three new edges so that connects and . If the resulting graph is supposed to 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, such as being planar[1] (when applied to a facial triangle) or linkless.[2] This fact is used to compactly describe the
A particularly relevant application exists in electrical engineering in the study of three-phase power systems (see Y-Δ transform (electrical engineering)).[3] 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 is the smallest family of graphs that contains and is closed under YΔ- and ΔY-transformations. Equivalently, it is constructed from by recursively applying these transformations until no new graph is generated. If 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 . It consists of the six forbidden minors for the class of linkless graphs.[2]
- the Heawood family is generated from and . It consists of 78 graphs, each of which is a forbidden minors for the class of 4-flat graphs.[4]
YΔY-reducible graphs
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
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: is not planar but YΔY-reducible, while the graph in the figure is not YΔY-reducible but linkless.[5]
References
- ^ Truemper, K. (1989). On the delta‐wye reduction for planar graphs. Journal of graph theory, 13(2), 141-148.
- ^ MR 1164063.
- ^ Johnson, D. E., Hilburn, J. L., Johnson, J. R., & Scott, P. D. (1986). Basic electric circuit analysis. Englewood Cliffs: Prentice-Hall.
- ^ van der Holst, H. (2006). Graphs and obstructions in four dimensions. Journal of Combinatorial Theory, Series B, 96(3), 388-404.
- ^ a b Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, pp. 100–101
- ^ Yu, Y. (2006). More forbidden minors for Wye-Delta-Wye reducibility. the electronic journal of combinatorics, R7-R7.