Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Discrete Mathematics and Combinatorics
Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh
Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh
LSU Doctoral Dissertations
``If a theorem about graphs can be expressed in terms of edges and cycles only, it probably exemplifies a more general theorem about matroids." Most of my work draws inspiration from this assertion, made by Tutte in 1979.
In 2004, Ehrenfeucht, Harju and Rozenberg proved that all graphs can be constructed from complete graphs via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. In Chapter 2, we consider the binary matroid analogue of each of these graph operations. We prove that the analogue of the result of Ehrenfeucht et. al. does …
Unavoidable Structures In Large And Infinite Graphs, Sarah Allred
Unavoidable Structures In Large And Infinite Graphs, Sarah Allred
LSU Doctoral Dissertations
In this work, we present results on the unavoidable structures in large connected and large 2-connected graphs. For the relation of induced subgraphs, Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either Kr or Kr. It is well known that, for every positive integer r, every sufficiently large connected graph contains an induced subgraph isomorphic to one of Kr, K1,r, and Pr. We prove an analogous result for 2-connected graphs. Similarly, for infinite graphs, every infinite connected graph contains an induced subgraph …