Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
-
- Indian Statistical Institute (12)
- Selected Works (8)
- Illinois Math and Science Academy (4)
- University of Kentucky (4)
- University of South Carolina (4)
-
- Western Michigan University (4)
- Bard College (2)
- Boise State University (2)
- Claremont Colleges (2)
- Louisiana State University (2)
- Marshall University (2)
- University of Richmond (2)
- Utah State University (2)
- California State University, San Bernardino (1)
- Dordt University (1)
- East Tennessee State University (1)
- Furman University (1)
- Georgia Southern University (1)
- Grand Valley State University (1)
- Louisiana Tech University (1)
- Loyola Marymount University and Loyola Law School (1)
- Montclair State University (1)
- Oberlin (1)
- Old Dominion University (1)
- Portland State University (1)
- Rose-Hulman Institute of Technology (1)
- University of Denver (1)
- University of New Mexico (1)
- University of South Florida (1)
- University of Texas at El Paso (1)
- Publication Year
- Publication
-
- Doctoral Theses (12)
- Noah Prince (5)
- Dissertations (4)
- Electronic Theses and Dissertations (4)
- Faculty Publications & Research (4)
-
- Theses and Dissertations (4)
- Theses and Dissertations--Mathematics (3)
- All Graduate Theses and Dissertations, Spring 1920 to Summer 2023 (2)
- LSU Doctoral Dissertations (2)
- Mathematics Faculty Publications and Presentations (2)
- Pomona Faculty Publications and Research (2)
- Branch Mathematics and Statistics Faculty and Staff Publications (1)
- Computer Science Faculty Publications (1)
- Department of Math & Statistics Faculty Publications (1)
- Department of Mathematics Facuty Scholarship and Creative Works (1)
- Doctoral Dissertations (1)
- Electronic Theses, Projects, and Dissertations (1)
- Faculty Publications (1)
- Faculty Work Comprehensive List (1)
- Furman University Electronic Journal of Undergraduate Mathematics (1)
- Graduate College Dissertations and Theses (1)
- Graduate Theses, Dissertations, and Problem Reports (1)
- Honors Papers (1)
- Honors Theses (1)
- Hua Kun Liu (1)
- Jennifer J. Quinn (1)
- Mathematics Faculty Publications (1)
- Mathematics Faculty Research (1)
- Mathematics Faculty Works (1)
- Mathematics Summer Fellows (1)
- Publication Type
- File Type
Articles 1 - 30 of 73
Full-Text Articles in Physical Sciences and Mathematics
On The Singular Pebbling Number Of A Graph, Harmony R. Morris
On The Singular Pebbling Number Of A Graph, Harmony R. Morris
Rose-Hulman Undergraduate Mathematics Journal
In this paper, we define a new parameter of a connected graph as a spin-off of the pebbling number (which is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble). This new parameter is the singular pebbling number, the smallest t such that a player can be given any configuration of at least t pebbles and any target vertex and can successfully move pebbles so that exactly one pebble ends on the target vertex. We also prove that the singular pebbling number of any graph on 3 or more vertices is equal …
Surjectivity Of The Wahl Map On Cubic Graphs, Angela C. Hanson
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.
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
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
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
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, polyHG, is the largest number of colors in an H-polychromatic coloring. We determine polyHG 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. …
Categorical Aspects Of Graphs, Jacob D. Ender
Categorical Aspects Of Graphs, Jacob D. Ender
Undergraduate Student Research Internships Conference
In this article, we introduce a categorical characterization of directed and undirected graphs, and explore subcategories of reflexive and simple graphs. We show that there are a number of adjunctions between such subcategories, exploring varying combinations of graph types.
Proper 3-Colorings Of Cycles And Hypercubes, Emily Cairncross
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
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 …
Doubly Chorded Cycles In Graphs, Maia Wichman
Doubly Chorded Cycles In Graphs, Maia Wichman
Student Scholars Day Oral Presentations
In 1963, Corradi and Hajnal proved that for any positive integer k if a graph contains at least 3k vertices and has minimum degree at least 2k, then it contains k disjoint cycles. This result is sharp, meaning there are graphs on at least 3k vertices with a minimum degree of 2k-1 that do not contain k disjoint cycles. Their work is the motivation behind finding sharp conditions that guarantee the existence of specific structures, e.g. cycles, chorded cycles, theta graphs, etc. In this talk, we will explore minimum degree conditions which guarantee a specific number of doubly chorded cycles, …
Graph-Theoretic Simplicial Complexes, Hajos-Type Constructions, And K-Matchings, Julianne Vega
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 …
On The Classification Of Vertex-Transitive Structures, John Clemens, Samuel Coskey, Stephanie Potter
On The Classification Of Vertex-Transitive Structures, John Clemens, Samuel Coskey, Stephanie Potter
Mathematics Faculty Publications and Presentations
We consider the classification problem for several classes of countable structures which are “vertex-transitive”, meaning that the automorphism group acts transitively on the elements. (This is sometimes called homogeneous.) We show that the classification of countable vertex-transitive digraphs and partial orders are Borel complete. We identify the complexity of the classification of countable vertex-transitive linear orders. Finally we show that the classification of vertex-transitive countable tournaments is properly above E0 in complexity.
Machine Learning Techniques As Applied To Discrete And Combinatorial Structures, Samuel David Schwartz
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
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, sdiamk(G), and the Steiner k-radius, sradk(G). In 1990, Henning, Oellermann and Swart [Ars Combinatoria 12 13-19, (1990)] showed that for any connected graph G, sdiam3(G) ≤(8/5)srad3(G) and …
Uniformly Connected Graphs, Nasreen Almohanna
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, …
On The Characteristic Polynomial Of A Hypergraph, Gregory J. Clark
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 …
Conventions, Habits, And U.S. Teachers’ Meanings For Graphs, Kevin C. Moore, Jason Silverman, Teo Paoletti, Dave Liss, Stacy Musgrave
Conventions, Habits, And U.S. Teachers’ Meanings For Graphs, Kevin C. Moore, Jason Silverman, Teo Paoletti, Dave Liss, Stacy Musgrave
Department of Mathematics Facuty Scholarship and Creative Works
In this paper, we use relevant literature and data to motivate a more detailed look into relationships between what we perceive to be conventions common to United States (U.S.) school mathematics and individuals’ meanings for graphs and related topics. Specifically, we draw on data from pre-service (PST) and in-service (IST) teachers to characterize such relationships. We use PSTs’ responses during clinical interviews to illustrate three themes: (a) some PSTs’ responses implied practices we perceive to be conventions of U.S. school mathematics were instead inherent aspects of PSTs’ meanings; (b) some PSTs’ responses implied they understood certain practices in U.S. school …
Applications Of Geometric And Spectral Methods In Graph Theory, Lauren Morey Nelsen
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
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
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.
Comparing Powers Of Edge Ideals, Mike Janssen, Thomas Kamp, Jason Vander Woude
Comparing Powers Of Edge Ideals, Mike Janssen, Thomas Kamp, Jason Vander Woude
Faculty Work Comprehensive List
Given a nontrivial homogeneous ideal I ⊆ k[x1, x2, . . . ,xd], a problem of great recent interest has been the comparison of the rth ordinary power of I and the mth symbolic power I(m). This comparison has been undertaken directly via an exploration of which exponents m and r guarantee the subset containment I(m) ⊆ Ir and asymptotically via a computation of the resurgence ρ(I), a number for which any m/r > ρ(I) guarantees I(m) ⊆ Ir. Recently, a third quantity, the symbolic defect, was introduced; as It ⊆ I(t), the symbolic defect is the minimal number of generators …
On Robust Colorings Of Hamming-Distance Graphs, Isaiah Harney, Heide Gluesing-Luerssen
On Robust Colorings Of Hamming-Distance Graphs, Isaiah Harney, Heide Gluesing-Luerssen
Mathematics Faculty Publications
Hq(n, d) is defined as the graph with vertex set Znq and where two vertices are adjacent if their Hamming distance is at least d. The chromatic number of these graphs is presented for various sets of parameters (q, n, d). For the 4-colorings of the graphs H2(n, n − 1) a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust 4-colorings of …
Persistence Equivalence Of Discrete Morse Functions On Trees, Yuqing Liu
Persistence Equivalence Of Discrete Morse Functions On Trees, Yuqing Liu
Mathematics Summer Fellows
We introduce a new notion of equivalence of discrete Morse functions on graphs called persistence equivalence. Two functions are considered persistence equivalent if and only if they induce the same persistence diagram. We compare this notion of equivalence to other notions of equivalent discrete Morse functions. We then compute an upper bound for the number of persistence equivalent discrete Morse functions on a fixed graph and show that this upper bound is sharp in the case where our graph is a tree. We conclude with an example illustrating our construction.
Graceful Colorings And Connection In Graphs, Alexis D. Byers
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 1 : E(G) → {1, 2, . . . , m} defined by f 1(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
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
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
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 + …
Ideas & Graphs, Martin Zwick
Ideas & Graphs, Martin Zwick
Systems Science Faculty Publications and Presentations
A graph can specify the skeletal structure of an idea, onto which meaning can be added by interpreting the structure.
This paper considers graphs (but not hypergraphs) consisting of four nodes, and suggests meanings that can be associated with several different directed and undirected graphs.
Drawing on Bennett's "systematics," specifically on the Tetrad that systematics offers as a model of 'activity,' the analysis here shows that the Tetrad is versatile model of problem-solving, regulation and control, and other processes.
A Method Based On Total Variation For Network Modularity Optimization Using The Mbo Scheme, Huiyi Hu, Thomas Laurent, Mason A. Porter, Andrea L. Bertozzi
A Method Based On Total Variation For Network Modularity Optimization Using The Mbo Scheme, Huiyi Hu, Thomas Laurent, Mason A. Porter, Andrea L. Bertozzi
Thomas Laurent
The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called “communities.” One popular approach to finding communities is to maximize a quality function known as modularity to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an $\ell_2$ balance term. By employing numerical techniques …
Colorings Of Hamming-Distance Graphs, Isaiah H. Harney
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 …