Discrete Mathematics and Combinatorics Commons^™

Hyper Face-Magic Graphs, Ross Belgram, Donald Mcginn

Theory & Applications of Graphs

For a planar graph G of order n, let F(G) be the set of all faces of G embedded into R 2 , including the exterior face. A bijective vertex labeling f : V (G) → {1, 2, ..., n} induces a face labeling f ∗ : F(G) → N defined by setting f ∗ (F) equal to the sum of all labels of the boundary vertices of F. The graph G is said to be hyper face-magic if there exists a vertex labeling whose induced face labeling is constant. In this paper, we state properties of hyper face-magic graphs …

From Total Domination To Graph Coloring, Sawyer Isaac Osborn

Dissertations

A question involving a chess piece called a prince on the 8×8 chessboard leads to a concept in graph theory involving total domination. We say a vertex u in a graph G totally dominates a vertex v if u is adjacent to v. A subset S of the vertex set of a graph G is a total dominating set for G if every vertex in G is totally dominated by at least one vertex of S. If S is a total dominating set of G, then σ_S(v) denotes the number of …

Dominating Hadwiger's Conjecture For 2k2-Free Graphs, Thomas Tibbetts

Honors Undergraduate Theses

A dominating K_t minor in a graph �� is a sequence (��₁,…,��_t) of pairwise disjoint non-empty connected subgraphs of ��, such that for 1≤��< ��≤��, every vertex in ��_j has a neighbor in ��_i. Replacing “every vertex in ��_j” by “some vertex in ��_j” retrieves the standard definition of a ��_t minor. The strengthened notion was introduced by Illingworth and Wood in 2024, who asked whether every graph with chromatic number �� contains a dominating ��_t minor. This is a substantial strengthening of the celebrated Hadwiger’s Conjecture, which asserts that every …

A Comprehensive Study Of Clique Graphs And Clique Regular Graphs, Connor Phillips

Senior Honors Projects, 2020-current

If Γ is a graph for which every edge is in exactly one clique of order ω, then one can form a new graph with vertex set equal to these cliques.  This is a generalization of the line graph of Γ.  We discover many general results and classifications related to these clique graphs that will be useful to researchers studying graphs with this property. In particular, we find bounds on the spectrum of Γ (with exact results when Γ is k-regular) and some complete classifications when Γ is strongly regular. We apply our results to derive novel information about the …

On Variations Of Isolation In Graphs, Geoffrey Boyer

All Dissertations

In 2015, Caro and Hansberg introduced a wonderful and natural generalization of the well-studied parameter of domination in graphs. For a graph $G$ and a family of graphs $\FF$, they define $S$ to be an $\FF$-isolating set if $G-N[S]$ contains no member of $\FF$ as a subgraph. The case where $\FF=\{K_1\}$ coincides with domination. The case where $\FF=\{K_2\}$ is now simply referred to as an isolating set. We strengthen known results about the isolation number of a graph, and explore variations of the parameter including the independent and total versions.

In particular for connected graphs of order $n$, a bound …

Unavoidable Immersions And Topological Minors Of K-Edge-Connected Graphs, Brittian Qualls

LSU Doctoral Dissertations

In this work, we present results concerning the unavoidable structures in large and infinite k-edge-connected graphs. These results are inspired by the classical result of Ramsey, who proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either K_r or $\overline{K_r}$. We consider different graph containment relations, focusing primarily on the immersion relation. In the case of finite graphs, we provide the unavoidable immersions of 4-edge-connected graphs and prove that linear edge-connectivity suffices to immerse the graph C_t,r.

This dissertation also considers infinite graphs. We present the …

Construction Techniques For Linear Realizations Of Multisets With Small Support, M. A. Ollis

Emerson Authors, Researchers, & Creators

The Buratti-Horak Rosa Conjecture is a problem in graph theory asking when we can find a Hamiltonian path in the complete graph that has various properties to do with edge lengths. In this paper, we use constructive methods to show that the conjecture is true for various parameter sets where it was previously unknown.

Modeling Virus Diffusion On Social Media Networks With The Smirq Model, Justin Browning, Arnav Mazumder, Gowri Nanda

Rose-Hulman Undergraduate Mathematics Journal

As social networking services become more complex and widespread, users become increasingly susceptible to becoming infected with malware and risk their data being compromised. In the United States, it costs the government billions of dollars annually to handle malware attacks. Additionally, computer viruses can be spread through schools, businesses, and individuals’ personal devices and accounts. Malware affecting larger groups of people causes problems with privacy, personal files, and financial security. Thus, we developed the probabilistic SMIRQ (pSMIRQ) model that shows how a virus spreads through a generated network as a way to track and prevent future viruses. Our model is …

The Forget Time For Random Walks On Trees Of A Fixed Diameter, Lola R. Vescovo

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk on a graph given a set of starting and stopping conditions. We study a mixing measure called the forget time. Given a graph G, the pessimal access time for a target distribution is the expected length of an optimal stopping rule to that target distribution, starting from the worst initial vertex. The forget time of G is the smallest pessimal access time among all possible target distributions. We prove that the balanced double broom maximizes the forget time on the set of trees on n vertices with diameter …

Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi

School of Computing: Dissertations, Theses, and Student Research

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …

Optimal Network Analysis Through Vertex Order Coloring Of Intuitionistic Fuzzy Graph Operations, A. Meenakshi, S. Dhanushiya, Hong Qin, Maniyandy Elangovan

Data Science Faculty Publications

Intuitionistic fuzzy graphs IFGs are a powerful tool for modeling uncertainty and complex relationships. They offer versatile frameworks for addressing real-world challenges. In this research, we have introduced intuitionistic fuzzy vertex order coloring IFVOC and analyzed the alpha-strong (alpha str), beta-strong (beta str), and gamma-strong (gamma str) vertices through their degree. We explored important theorems based on the types of strong vertices, broadening the scope of our study. We analyzed multiple IFG products to determine the most optimal network based on some important metrics, including the weight and total number of alpha str vertices, the chromatic number, and the weight …

Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham

All Theses

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

Combinatorially Orthogonal Paths, Sean A. Bailey, David E. Brown, Leroy Beaseley

Communications on Number Theory and Combinatorial Theory

Vectors x=(x₁,x₂,...,x_n)^T and y=(y₁,y₂,...,y_n)^T are combinatorially orthogonal if |{i:x_iy_i≠0}|≠1. An undirected graph G=(V,E) is a combinatorially orthogonal graph if there exists f:V→ℝⁿ such that for any u,v∈V, uv∉E iff f(u) and f(v) are combinatorially orthogonal. We will show that every graph has a combinatorially orthogonal representation. We will show …

The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales

Rose-Hulman Undergraduate Mathematics Journal

DNA and other polymer chains in confined spaces behave like closed loops. Arsuaga et al. \cite{AB} introduced the uniform random polygon model in order to better understand such loops in confined spaces using probabilistic and knot theoretical techniques, giving some classification on the mean squared linking number of such loops. Flapan and Kozai \cite{flapan2016linking} extended these techniques to find the mean sum of squared linking numbers for random linear embeddings of complete graphs $K_n$ and found it to have order $\Theta(n(n!))$. We further these ideas by inspecting random piecewise-linear embeddings of complete graphs and give introductory-level summaries of the ideas …

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Mixing Measures For Trees Of Fixed Diameter, Ari Holcombe Pomerance

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk in a graph given a set of starting and stopping conditions. We determine the tree structures of order n with diameter d that minimize and maximize for a few mixing measures. We show that the maximizing tree is usually a broom graph or a double broom graph and that the minimizing tree is usually a seesaw graph or a double seesaw graph.

Zonality In Graphs, Andrew Bowling

Dissertations

Graph labeling and coloring are among the most popular areas of graph theory due to both the mathematical beauty of these subjects as well as their fascinating applications. While the topic of labeling vertices and edges of graphs has existed for over a century, it was not until 1966 when Alexander Rosa introduced a labeling, later called a graceful labeling, that brought the area of graph labeling to the forefront in graph theory. The subject of graph colorings, on the other hand, goes back to 1852 when the young British mathematician Francis Guthrie observed that the countries in a map …

Irregular Domination In Graphs, Caryn Mays

Dissertations

Domination in graphs has been a popular area of study due in large degree to its applications to modern society as well as the mathematical beauty of the topic. While this area evidently began with the work of Claude Berge in 1958 and Oystein Ore in 1962, domination did not become an active area of research until 1977 with the appearance of a survey paper by Ernest Cockayne and Stephen Hedetniemi. Since then, a large number of variations of domination have surfaced and provided numerous applications to different areas of science and real-life problems. Among these variations are domination parameters …

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.

Iterated Jump Graphs, Fran Herr, Legrand Jones Ii

Rose-Hulman Undergraduate Mathematics Journal

The jump graph J(G) of a simple graph G has vertices which represent edges in G where two vertices in J(G) are adjacent if and only if the corresponding edges in G do not share an endpoint. In this paper, we examine sequences of graphs generated by iterating the jump graph operation and characterize the behavior of this sequence for all initial graphs. We build on work by Chartrand et al. who showed that a handful of jump graph sequences terminate and two sequences converge. We extend these results by showing that there are no non-trivial repeating sequences of jump …

The Chromatic Index Of Ring Graphs, Lilian Shaffer

Rose-Hulman Undergraduate Mathematics Journal

The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or …

Methods Of Computing Graph Gonalities, Noah Speeter

Theses and Dissertations--Mathematics

Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is …

Selected Problems In Graph Coloring, Hudson Lafayette

Theses and Dissertations

The Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4.

For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.

Rainbow Turan Methods For Trees, Victoria Bednar

Theses and Dissertations

The rainbow Turan number, a natural extension of the well-studied traditional
Turan number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstraete. The rainbow Tur ́an number of a graph F , ex*(n, F ), is the largest number of edges for an n vertex graph G that can be properly edge colored with no rainbow F subgraph. Chapter 1 of this dissertation gives relevant definitions and a brief history of extremal graph theory. Chapter 2 defines k-unique colorings and the related k-unique Turan number and provides preliminary results on this new variant. In Chapter 3, we explore the …

Counting Spanning Trees On Triangular Lattices, Angie Wang

CMC Senior Theses

This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …

On Prime Labelings Of Uniform Cycle Snake Graphs, M. A. Ollis

Emerson Authors, Researchers, & Creators

A reseaech paper in graph theory, a subfield of math. At the time of the research Agam Bedi and Samiksha Ramesh were undergraduate students at Emerson College and the work was completed as part of the SOC320 Research Co-Curricular in the summer of 2022. The work has a Creative Commons BY-NC licence.

Investigations In The Semi-Strong Product Of Graphs And Bootstrap Percolation, Kevin J. Mccall

Theses and Dissertations

The semi-strong product of graphs G and H is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) x V(H). The edges of the semi-strong product are determined as follows: (g₁,h₁)(g₂,h₂) is an edge of the product whenever g₁g₂ is an edge of G and h₁h₂ is an edge of H or g₁ = g₂ and h₁h_{2 …}

Kōlams In Graph Theory: Mathematics In South Indian Ritual Art, Nathan Hartmann

Murray State Theses and Dissertations

Kōlams are a ritual art form found in India, most commonly in the southern state
of Tamil Nadu. Comprised of different interlocking knots, these women-drawn designs are placed on the entrances to people’s home to showcase the household’s emotional state and ask the earth goddess Bhūdevi for forgiveness. More aesthetically pleasing kōlams are considered latshanam, where the design permeates beauty; monolinearity is one such aspect that implements latshanam. Using graph theory, we examine one style of these drawings, the labyrinthine variety, to identify if a given kōlam is monolinear and how to construct monolinear kōlams.

Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox

Theory & Applications of Graphs

In [Abueida, A. and Roblee, K., More harmonious labelings of families of disjoint unions of an odd cycle and certain trees, J. Combin. Math. Combin. Comput., 115 (2020), 61-68] it is shown that the disjoint union of an odd cycle and certain paths is harmonious, and that certain starlike trees are harmonious using properties of cosets for a particular subgroup of the integers modulo m, where m is the number of edges of the graph. We expand upon these results by first exploring the numerical properties when adding values from cosets and subcosets in the integers modulo m. …

3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel Mccann

Mathematical Sciences Undergraduate Honors Theses

The complete 3-uniform hypergraph of order v is denoted as K_v and consists of vertex set V with size v and edge set E, containing all 3-element subsets of V. We consider a 3-uniform hypergraph P₇, a path with vertex set {v₁, v₂, v₃, v₄, v₅, v₆, v₇} and edge set {{v₁, v₂, v₃}, {v₂, v₃, v₄}, {v₄, v₅, v₆}, {v₅, v_{6 …}