Skip to main content

Rooted Minors and Delta-Wye Transformations

Resource type
Thesis type
(Thesis) Ph.D.
Date created
2012-10-02
Authors/Contributors
Abstract
In this thesis, we study terminal minors and delta-wye reducibility. The concept of terminal minors extends the notion of graph minors to the case where we have a distinguished set of vertices $T$ in our graph $G$ that must correspond to a distinguished set of vertices $Y$ in the minor. Delta-wye reducibility concerns the study of how graphs can be reduced under a set of six operations: the four series-parallel reductions, delta-wye, and wye-delta transformations. For terminal minors, we completely characterize when, given a planar graph with four terminals, we can find a minor of $K_{2,4}$ in that graph with the four terminal vertices forming the larger part of the bipartition. This is an extension of a result due to Robertson and Seymour for the case when a graph contains three terminals. For delta-wye reducibility, we study the problem of reducibility for the class of graphs consisting of four-terminal planar graphs. Using the results about rooted $K_{2,4}$ minors, we are able to characterize when 3-connected graphs in this class are reducible.
Document
Identifier
etd7556
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection
Download file Size
etd7556_LDemasi.pdf 1.17 MB

Views & downloads - as of June 2023

Views: 60
Downloads: 2