Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 83-93 |
Number of pages | 11 |
Journal | Journal of Graph Theory |
Volume | 33 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2000 |
Externally published | Yes |
Keywords
- Reducible graphs
- Terminal
- Wye-delta
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics