Title page for ETD etd-0529103-123537


Type of Document Dissertation
Author Kanno, Jinko
Author's Email Address jkanno1@lsu.edu
URN etd-0529103-123537
Title Splitter Theorems for 3- and 4-Regular 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
  • non-simple graphs
  • edge reduction
Date of Defense 2003-05-01
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 HG with GH, then there is a decreasing sequence of graphs from G to H, say G=G0≥G1≥G2...Gt=H, all intermediate graphs are in g, and each Gi can be obtained from Gi-1 by applying a single operation in O.

The classes of graphs that we consider are either 3-regular or 4-regular 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 3-regular 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 4-regular 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)   Higher-speed Access 
  Kanno_dis.pdf 757.15 Kb 00:03:30 00:01:48 00:01:34 00:00:47 00:00:04

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LSU-ETD Support.