𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Forbidden minors for wye-delta-wye reducibility

✍ Scribed by Yaming Yu

Book ID
102343527
Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
57 KB
Volume
47
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is Y Δ Y reducible if it can be reduced to a single vertex by a sequence of series‐parallel reductions and Y Δ Y transformations. The class of Y Δ Y reducible graphs is minor closed. We found a large number of minor minimal Y Δ Y irreducible graphs: a family of 57578 31‐edge graphs and another 40‐edge graph. It is still an open problem to characterize Y Δ Y reducible graphs in terms of a finite set of forbidden minors. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 47: 317–321, 2004

πŸ“œ SIMILAR VOLUMES

Four-terminal reducibility and projectiv
Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs
✍ Archdeacon, Dan; Colbourn, Charles J.; Gitler, Isidoro; Provan, J. Scott πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 188 KB

A graph is Y βˆ†Y -reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and Y βˆ†Y -transformations. Terminals are dis-

On terminal delta-wye reducibility of pl
On terminal delta-wye reducibility of planar graphs
✍ Isidoro Gitler; FeliΓΊ Sagols πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 614 KB

We prove terminal -Y reducibility of planar graphs with at most three terminals. The most important consequence of our proof is that this implicitly gives an efficient algorithm with time complexity O(|E (G)| 4 ) for reducibility of planar graphs G with at most three terminals. It also can be used f

On the delta-wye reduction for planar gr
On the delta-wye reduction for planar graphs
✍ K. Truemper πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 367 KB

We provide an elementary proof of an important theorem by G. V. Epifanov, according to which every two-terminal planar graph satisfying certain connectivity restrictions can by some sequence of series/parallel reductions and delta-wye exchanges be reduced to the graph consisting of the two terminals