Discrete Mathematics and Combinatorics Commons^™

Surjectivity Of The Wahl Map On Cubic Graphs, Angela C. Hanson

Theses and Dissertations--Mathematics

Much of algebraic geometry is the study of curves. One tool we use to study curves is whether they can be embedded in a K3 surface or not. If the Wahl map is surjective on a curve, that curve cannot be embedded in a K3 surface. Therefore, studying if the Wahl map is surjective for a particular curve gives us more insight into the properties of that curve. We simplify this problem by converting graph curves to dual graphs. Then the information for graphs can be used to study the underlying curves. We will discuss conditions for the Wahl map …

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 …

Polychromatic Colorings Of Certain Subgraphs Of Complete Graphs And Maximum Densities Of Substructures Of A Hypercube, Ryan Tyler Hansen

Graduate Theses, Dissertations, and Problem Reports

If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, poly_HG, is the largest number of colors in an H-polychromatic coloring. We determine poly_HG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q. …

On Hamilton Cycle Decompositions Of Complete Multipartite Graphs Which Are Both Cyclic And Symmetric, Fatima A. Akinola

Theses, Dissertations and Capstones

Let G be a graph with v vertices. A Hamilton cycle of a graph is a collection of edges which create a cycle using every vertex. A Hamilton cycle decomposition is cyclic if the set of cycle is invariant under a full length permutation of the vertex set. We say a decomposition is symmetric if all the cycles are invariant under an appropriate power of the full length permutation. Such decompositions are known to exist for complete graphs and families of other graphs. In this work, we show the existence of cyclic n-symmetric Hamilton cycle decompositions of a family …

Graph-Theoretic Simplicial Complexes, Hajos-Type Constructions, And K-Matchings, Julianne Vega

Theses and Dissertations--Mathematics

A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph G and a monotone graph property P, one can associate to the pair (G,P) a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these graph-theoretic simplicial complexes using combinatorial and topological approaches as a way to inform our understanding of the graphs and their properties.

In this dissertation, we study two families of simplicial complexes: (1) neighborhood complexes and (2) k-matching complexes. A neighborhood complex is a simplicial …

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph G …

Colorings Of Hamming-Distance Graphs, Isaiah H. Harney

Theses and Dissertations--Mathematics

Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into …

Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon

Electronic Theses, Projects, and Dissertations

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

Graphs Of Classroom Networks, Rebecca Holliday

Electronic Theses and Dissertations

In this work, we use the Havel-Hakimi algorithm to visualize data collected from students to investigate classroom networks. The Havel-Hakimi algorithm uses a recursive method to create a simple graph from a graphical degree sequence. In this case, the degree sequence is a representation of the students in a classroom, and we use the number of peers with whom a student studied or collaborated to determine the degree of each. We expand upon the Havel-Hakimi algorithm by coding a program in MATLAB that generates random graphs with the same degree sequence. Then, we run another algorithm to find the isomorphism …

Omnisculptures., Cihan Eroglu

Electronic Theses and Dissertations

In this thesis we will study conditions for the existence of minimal sized omnipatterns in higher dimensions. We will introduce recent work conducted on one dimensional and two dimensional patterns known as omnisequences and omnimosaics, respectively. These have been studied by Abraham et al [3] and Banks et al [2]. The three dimensional patterns we study are called omnisculptures, and will be the focus of this thesis. A (K,a) omnisequence of length n is a string of letters that contains each of the a^k words of length k over [A]={1,2,...a} as a substring. …