Digital Commons Network^™

On Properties Of Matroid Connectivity, Simon Pfeil

LSU Doctoral Dissertations

Highly connected matroids are consistently useful in the analysis of matroid structure. Round matroids, in particular, were instrumental in the proof of Rota's conjecture. Chapter 2 concerns a class of matroids with similar properties to those of round matroids. We provide many useful characterizations of these matroids, and determine explicitly their regular members. Tutte proved that a 3-connected matroid with every element in a 3-element circuit and a 3-element cocircuit is either a whirl or the cycle matroid of a wheel. This result led to the proof of the 3-connected splitter theorem. More recently, Miller proved that matroids of sufficient …

Selected Problems On Matroid Minors, Jesse Taylor

LSU Doctoral Dissertations

This dissertation begins with an introduction to matroids and graphs. In the first chapter, we develop matroid and graph theory definitions and preliminary results sufficient to discuss the problems presented in the later chapters. These topics include duality, connectivity, matroid minors, and Cunningham and Edmonds's tree decomposition for connected matroids. One of the most well-known excluded-minor results in matroid theory is Tutte's characterization of binary matroids. The class of binary matroids is one of the most widely studied classes of matroids, and its members have many attractive qualities. This motivates the study of matroid classes that are close to being …

Refining The Characterization Of Projective Graphs, Perry K. Iverson

LSU Doctoral Dissertations

Archdeacon showed that the class of graphs embeddable in the projective plane is characterized by a set of 35 excluded minors. Robertson, Seymour and Thomas in an unpublished result found the excluded minors for the class of k-connected graphs embeddable on the projective plane for k = 1,2,3. We give a short proof of that result and then determine the excluded minors for the class of internally 4-connected projective graphs. Hall showed that a 3-connected graph diff_x000B_erent from K5 is planar if and only if it has K3,3 as a minor. We provide two analogous results for projective graphs. For …

Excluded-Minor Characterization Of Apex-Outerplanar Graphs, Stanislaw Dziobiak

LSU Doctoral Dissertations

It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K_4 and K_{2,3}. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this class.

Some Classes Of Graphs That Are Nearly Cycle-Free, Lisa Warshauer

LSU Doctoral Dissertations

A graph is almost series-parallel if there is some edge that one can add to the graph and then contract out to leave a series-parallel graph, that is, a graph with no K₄-minor. In this dissertation, we find the full list of excluded minors for the class of graphs that are almost series-parallel. We also obtain the corresponding result for the class of graphs such that uncontracting an edge and then deleting the uncontracted edge produces a series-parallel graph.

A notable feature of a 3-connected almost series-parallel graph is that it has two vertices whose removal leaves a …