Physical Sciences and Mathematics 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 …

Computing Well-Structured Subgraphs In Geometric Intersection Graphs., Satyabrata Jana Dr.

Doctoral Theses

For a set of geometric objects, the associative geometric intersection graph is the graph with a vertex for each object and an edge between two vertices if and only if the corresponding objects intersect. Geometric intersection graphs are very important due to their theoretical properties and applicability. Based on the different geometric objects, several types of geometric intersection graphs are defined. Given a graph G, an induced (either vertex or edge) subgraph H ⊆ G is said to be an well-structured subgraph if H satisfies certain properties among the vertices in H. This thesis studies some well-structured subgraphs finding problems …

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 …

Graph Realizability And Factor Properties Based On Degree Sequence, Daniel John

Electronic Theses and Dissertations

A graph is a structure consisting of a set of vertices and edges. Graph construction has been a focus of research for a long time, and generating graphs has proven helpful in complex networks and artificial intelligence.

A significant problem that has been a focus of research is whether a given sequence of integers is graphical. Havel and Hakimi stated necessary and sufficient conditions for a degree sequence to be graphic with different properties. In our work, we have proved the sufficiency of the requirements by generating algorithms and providing constructive proof.

Given a degree sequence, one crucial problem is …

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. …

Proper 3-Colorings Of Cycles And Hypercubes, Emily Cairncross

Honors Papers

In this paper, we look at two families of graphs, cycles and hypercubes, and compare how their sets of proper 3-colorings differ as the graphs get arbitrarily large. In particular, we find the probability of pairs of vertices at various distances being the same color in order to understand the range and scale of interactions between them. As we look at larger and larger cycles, larger and larger hypercubes, patterns begin to emerge. While the colors of vertices fixed fractions of the cycle away from each other are independent, a random 3-coloring of the hypercube is essentially a 2-coloring. This …

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 …

Machine Learning Techniques As Applied To Discrete And Combinatorial Structures, Samuel David Schwartz

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Machine Learning Techniques have been used on a wide array of input types: images, sound waves, text, and so forth. In articulating these input types to the almighty machine, there have been all sorts of amazing problems that have been solved for many practical purposes.

Nevertheless, there are some input types which don’t lend themselves nicely to the standard set of machine learning tools we have. Moreover, there are some provably difficult problems which are abysmally hard to solve within a reasonable time frame.

This thesis addresses several of these difficult problems. It frames these problems such that we can …

A Few Problems On The Steiner Distance And Crossing Number Of Graphs, Josiah Reiswig

Theses and Dissertations

We provide a brief overview of the Steiner ratio problem in its original Euclidean context and briefly discuss the problem in other metric spaces. We then review literature in Steiner distance problems in general graphs as well as in trees.

Given a connected graph G we examine the relationship between the Steiner k-diameter, sdiam_k(G), and the Steiner k-radius, srad_k(G). In 1990, Henning, Oellermann and Swart [Ars Combinatoria 12 13-19, (1990)] showed that for any connected graph G, sdiam₃(G) ≤(8/5)srad₃(G) and …

On The Characteristic Polynomial Of A Hypergraph, Gregory J. Clark

Theses and Dissertations

We consider the computation of the adjacency characteristic polynomial of a uniform hypergraph. Computing the aforementioned polynomial is intractable, in general; however, we present two mechanisms for computing partial information about the spectrum of a hypergraph as well as a methodology (and in particular, an algo- rithm) for combining this information to determine complete information about said spectrum. The first mechanism is a generalization of the Harary-Sachs Theorem for hypergraphs which yields an explicit formula for each coefficient of the characteristic polynomial of a hypergraph as a weighted sum over a special family of its subgraphs. The second is a …

Uniformly Connected Graphs, Nasreen Almohanna

Dissertations

Perhaps the most fundamental property that a graph can possess is that of being connected. Two vertices u and v of a graph G are connected if G contains a u-v path. The graph G itself is connected if every two vertices of G are connected. The well-studied concept of connectivity provides a measure on how strongly connected a graph may be. There are many other degrees of connectedness for a graph. A Hamiltonian path in a graph G is a path containing every vertex of G. Among the best-known classes of highly connected graph are the Hamiltonian-connected graphs, …

Applications Of Geometric And Spectral Methods In Graph Theory, Lauren Morey Nelsen

Electronic Theses and Dissertations

Networks, or graphs, are useful for studying many things in today’s world. Graphs can be used to represent connections on social media, transportation networks, or even the internet. Because of this, it’s helpful to study graphs and learn what we can say about the structure of a given graph or what properties it might have. This dissertation focuses on the use of the probabilistic method and spectral graph theory to understand the geometric structure of graphs and find structures in graphs. We will also discuss graph curvature and how curvature lower bounds can be used to give us information about …

Analysing Flow Free With One Pair Of Dots, Eliot Harris Roske

Senior Projects Spring 2019

Flow Free is a smartphone puzzle game where the player is presented with an m by m grid containing multiple pairs of colored dots. In order to solve the puzzle, the player must draw a path connecting each pair of points so that the following conditions are met: each pair of dots is connected by a path, each square of the grid is crossed by a path, and no paths intersect. Based on these puzzles, this project looks at grids of size m by n with only one pair of dots to determine for which configurations of dots a solution …

Kings In The Direct Product Of Digraphs, Morgan Norge

Theses and Dissertations

A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.

Graceful Colorings And Connection In Graphs, Alexis D. Byers

Dissertations

For a graph G of size m, a graceful labeling of G is an injective function f : V (G) → {0, 1, . . . , m} that gives rise to a bijective function f ¹ : E(G) → {1, 2, . . . , m} defined by f ¹(uv) = |f (u) − f (v)|. A graph is graceful if it has a graceful labeling. Over the years, a number of variations of graceful …

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 …

Networks, (K)Nots, Nucleotides, And Nanostructures, Ada Morse

Graduate College Dissertations and Theses

Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of …

Quick Trips: On The Oriented Diameter Of Graphs, Garner Paul Cochran

Theses and Dissertations

In this dissertation, I will discuss two results on the oriented diameter of graphs with certain properties. In the first problem, I studied the oriented diameter of a graph G. Erdos et al. in 1989 showed that for any graph with |V | = n and δ(G) = δ the maximum the diameter could possibly be was 3 n/ δ+1. I considered whether there exists an orientation on a given graph with |G| = n and δ(G) = δ that has a small diameter. Bau and Dankelmann (2015) showed that there is an orientation of diameter 11 n/ δ+1 + …

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.

Exploring Tournament Graphs And Their Win Sequences, Sadiki O. Lewis

Senior Projects Fall 2016

In this project we will be looking at tournaments on graphs and their win sequences. The main purpose for a tournament is to determine a winner amongst a group of competitors. Usually tournaments are played in an elimination style where the winner of a game advances and the loser is knocked out the tournament. For the purpose of this project I will be focusing on Round Robin Tournaments where all competitors get the opportunity to play against each other once. This style of tournaments gives us a more real life perspective of a fair tournament. We will model these Round …

Edge Colorings Of Graphs And Their Applications, Daniel Johnston

Dissertations

Edge colorings have appeared in a variety of contexts in graph theory. In this work, we study problems occurring in three separate settings of edge colorings.

For more than a quarter century, edge colorings have been studied that induce vertex colorings in some manner. One research topic we investigate concerns edge colorings belonging to this class of problems. By a twin edge coloring of a graph G is meant a proper edge coloring of G whose colors come from the integers modulo k that induce a proper vertex coloring in which the color of a vertex is the sum of …

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 …

On Eulerian Irregularity And Decompositions In Graphs, Eric Andrews

Dissertations

Abstract attached as separate file.

Hamiltonicity, Pancyclicity, And Cycle Extendability In Graphs, Deborah C. Arangno

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

A significant portion of Graph Theory is devoted to determining the characteristics which guarantee the existence of long cycles.

Long cycles have roles in applications to civil engineering, chemistry, and communications, among many others, but the problem, in and of itself, of determining whether a graph has a cycle of some fixed and typically large length is one of the most important problems of both pure Mathematics and Computer Science.

A cycle containing all the vertices of the graph is called a Hamiltonian cycle, and a graph which possesses such a cycle is said to be Hamiltonian. If …

Dihedral Cayley Directed Strongly Regular Graphs, Jose Jonathan Gamez

Open Access Theses & Dissertations

A graph is a directed strongly regular graph (DSRG) if and only if the number of paths of length 2 from x to y is: λ, if there is an edge from x to y; μ, if there is not an edge from x to y (with x not equal to y); and t, if x = y. For every vertex in G, the in-degree and out-degree is k. The number of vertices in G is denoted by v. If G is a group and S a subset of G, then the …

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. …

Fundamental Transversals On The Complexes Of Polyhedra, Joy D'Andrea

USF Tampa Graduate Theses and Dissertations

We present a formal description of `Face Fundamental Transversals' on the faces of the Complexes of polyhedra (meaning threedimensional polytopes). A Complex of a polyhedron is the collection of the vertex points of the polyhedron, line segment edges and polygonal faces of the polyhedron. We will prove that for the faces of any 3-dimensional complex of a polyhedron under face adjacency relations, that a `Face Fundamental Transversal' exists, and it is a union of the connected orbits of faces that are intersected exactly once. While exploring the problem of finding a face fundamental transversal, we have found a partial result …

Obstruction Sets For Classes Of Cubic Graphs, Joshua Hughes

Doctoral Dissertations

This dissertation establishes two theorems which characterize the set of minimal obstructions for two classes of graphs. A minimal obstruction for a class of graphs is a graph that is not in the class but every graph that it properly contains, under some containment relation, is in the class. In Chapter 2, we provide a characterization of the class of cubic outer-planar graphs in terms of its minimal obstructions which are also called cubic obstructions in this setting. To do this, we first show that all the obstructions containing loops can be obtained from the complete set of loopless obstructions …