Title page for ETD etd-07072006-090411

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
  • decomposition
  • crossing 3-separation
  • flower
  • hamiltonian
  • pancyclic
  • 3-tree
  • 3-connected
Date of Defense 2006-07-03
Availability unrestricted
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.

  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

Browse All Available ETDs by ( Author | Department )

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