
Type of Document Dissertation Author Kanno, Jinko Author's Email Address jkanno1@lsu.edu URN etd0529103123537 Title Splitter Theorems for 3 and 4Regular Graphs Degree Doctor of Philosophy (Ph.D.) Department Mathematics Advisory Committee
Advisor Name Title Guoli Ding Committee Chair Bogdan Oporowski Committee Member Patrick Gilmer Committee Member Raymond Fabec Committee Member William Hoffman Committee Member Charles Harlow Dean's Representative Keywords
 adding handles
 girth four
 nonsimple graphs
 edge reduction
Date of Defense 20030501 Availability unrestricted Abstract Let g be a class of graphs and ≤ be a graph containment relation. A splitter theorem for g under ≤ is a result that claims the existence of a set O of graph operations such that if G and H are in g and H≤G with G≠H, then there is a decreasing sequence of graphs from G to H, say G=G_{0}≥G_{1}≥G_{2}...G_{t}=H, all intermediate graphs are in g, and each G_{i} can be obtained from G_{i1} by applying a single operation in O.
The classes of graphs that we consider are either 3regular or 4regular that have various connectivity and girth constraints. The graph containment relation we are going to consider is the immersion relation. It is worth while to point out that, for 3regular graphs, this relation is equivalent to the topological minor relation. We will also look for the minimal graphs in each family. By combining these results with the corresponding splitter theorems, we will have several generating theorems.
In Chapter 4, we investigate 4regular planar graphs. We will see that planarity makes the problem more complicated than in the previous cases. In Section 4.5, we will prove that our results in Chapter 4 are the best possible if we only allow finitely many graph operations.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higherspeed Access Kanno_dis.pdf 757.15 Kb 00:03:30 00:01:48 00:01:34 00:00:47 00:00:04