Type of Document Dissertation Author Beavers, Brian Daniel Author's Email Address firstname.lastname@example.org URN etd-07072006-090411 Title Circuits and Structure in Matroids and Graphs Degree Doctor of Philosophy (Ph.D.) Department Mathematics Advisory Committee
Advisor Name Title James Oxley Committee Chair George Cochran Committee Member Guoli Ding Committee Member Richard Litherland Committee Member Robert Perlis Committee Member Sukhamay Kundu Dean's Representative Keywords
- crossing 3-separation
Date of Defense 2006-07-03 Availability unrestricted AbstractThis dissertation consists of several results on matroid and graph structure and is organized into three main parts. The main goal of the first part, Chapters 1-3, is to produce a unique decomposition of 3-connected matroids into more highly connected pieces. In Chapter 1, we review the definitions and main results from the previous work of Hall, Oxley, Semple, and Whittle. In Chapter 2, we introduce operations that allow us to decompose a 3-connected matroid M into a pair of 3-connected pieces by breaking the matroid apart at a 3-separation. We also generalize a result of Akkari and Oxley. In Chapter 3, we produce the decomposition. We analyze the properties of equivalent 3-separations and then use these properties to create a decomposition tree that is labeled by subsets of M. We then use the decomposition tree as a guide to show us where to break M apart.
The second part, Chapter 4, specializes the results of the first part to graphs. Given a simple 3-connected graph G, we first analyze the properties of G that come from the presence of crossing 3-separations in its cycle matroid. We prove that specializing the decomposition in Chapter 3 gives us a decomposition of G into graphs whose cycle matroids are sequentially 4-connected. We show that every simple 3-connected graph whose cycle matroid is sequential is a minor of certain special planar graphs that we call sequential 3-paths. We also prove that a sequential 3-connected binary matroid is a 3-connected minor of the cycle matroid of a sequential 3-path.
The third part, Chapter 5, explores the presence of circuits of various sizes in simple representable matroids. We prove that a sufficiently large, simple binary matroid either has circuits of all sizes or is isomorphic to one of two exceptions. We also show that, up to isomorphism, all but six sufficiently large, simple binary matroids have Hamiltonian circuits through each element.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Beavers_dis.pdf 7.37 Mb 00:34:06 00:17:32 00:15:20 00:07:40 00:00:39
If you have questions or technical problems, please Contact LSU-ETD Support.