Title page for ETD etd-06302009-171138


Type of Document Dissertation
Author Morgan, Evan
URN etd-06302009-171138
Title Some Results on Cubic Graphs
Degree Doctor of Philosophy (Ph.D.)
Department Mathematics
Advisory Committee
Advisor Name Title
Bogdan Oporowski Committee Chair
James Madden Committee Member
James Oxley Committee Member
Jerome Hoffman Committee Member
Robert Perlis Committee Member
Luis Lehner Dean's Representative
Keywords
  • minor
Date of Defense 2009-06-08
Availability unrestricted
Abstract
Pursuing a question of Oxley, we investigate whether the edge set of a graph admits a bipartition so that the contraction of either partite set produces a series-parallel graph. While Oxley's question in general remains unanswered, our investigations led to two graph operations (Chapters 2 and 4) which are of independent interest. We present some partial results toward Oxley's question in Chapter 3.

The central results of the dissertation involve an operation on cubic graphs called the switch; in the literature, a similar operation is known as the edge slide. In Chapter 2, the author proves that we can transform, with switches, any connected, cubic graph on n vertices into any other connected, cubic graph on n vertices. Furthermore, connectivity, up to internal 4-connectedness, can be preserved during the operations.

In 2007, Demaine, Hajiaghayi, and Mohar proved the following: for a fixed genus g and any integer k greater than or equal to 2, and for every graph G of Euler genus at most g, the edges of G can be partitioned into k sets such that contracting any one of the sets produces a graph of tree-width at most O(g^2 k). In Chapter 3 we sharpen this result, when k=2, for the projective plane (g=1) and the torus (g=2).

During early simultaneous investigations of Jaeger's Dual-Hamiltonian conjecture and Oxley's question, we obtained a simple structure theorem on cubic, internally 4-connected graphs. That result is found in Chapter 4.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  morgan_diss.pdf 578.85 Kb 00:02:40 00:01:22 00:01:12 00:00:36 00:00:03

Browse All Available ETDs by ( Author | Department )

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