Graph immersions

Author: 
Date created: 
2018-11-27
Identifier: 
etd19986
Keywords: 
Immersion
Weak immersion
Edge-connectivity
Splitter theorem
Chain theorem
Structural theorem
Abstract: 

One of the first prominent theorems in structural graph theory is the Kuratowski-Wagner theorem which characterizes planar graphs as those with no K_{3,3} or K_5 minor. Numerous other classical theorems give precise descriptions of the class of graphs with no H-minor for numerous small graphs H. In particular, such classifications exist when H is W_4, W_5, Prism, K_{3,3}, K_5, Octahedron, and Cube. One of the most useful tools in establishing such results are splitter theorems which reduce a graph while preserving both connectivity and containment of a given minor. In this thesis we consider analogous problems for a different containment relation: immersion. Although immersion is a standard containment relation, prior to this thesis there were almost no precise structure theorems for forbidden immersions. The most prominent theorems in this direction give a rough description of graphs with no W_4 immersion and those with no K_{3,3} or K_5 immersion. Our main contributions include precise structure theorems for the class of graphs with no H-immersion when H is one of K_4, W_4, Prism, and K_{3,3}. To assist in this exploration, we have also established two splitter theorems for graph immersions, one for 2k-edge-connected graphs, and another for 3-edge-connected and internally 4-edge-connected graphs.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Matt DeVos
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.
Statistics: