Premium
Four‐terminal reducibility and projective‐planar wye‐delta‐wye‐reducible graphs
Author(s) -
Archdeacon Dan,
Colbourn Charles J.,
Gitler Isidoro,
Provan J. Scott
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200002)33:2<83::aid-jgt3>3.0.co;2-p
Subject(s) - combinatorics , mathematics , planar graph , vertex (graph theory) , discrete mathematics , 1 planar graph , graph , chordal graph
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 distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four‐terminal planar graphs are Y Δ Y ‐reducible when at least three of the vertices lie on the same face. Using this result, we characterize Y Δ Y ‐reducible projective‐planar graphs. We also consider terminals in projective‐planar graphs, and establish that graphs of crossing‐number one are Y Δ Y ‐reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000