Type of Document	Dissertation
Author	Beavers, Brian Daniel
Author's Email Address	thebeavs@yahoo.com
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	decomposition crossing 3-separation flower hamiltonian pancyclic 3-tree 3-connected
Date of Defense	2006-07-03
Availability	unrestricted
Abstract This 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.
Files	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.