Discrete Mathematics and Combinatorics Commons^™

Failed Zero Forcing Numbers Of Trees And Circulant Graphs, Luis Gomez, Karla Rubi, Jorden Terrazas, Rigoberto Florez, Darren A. Narayan

Theory & Applications of Graphs

Given a graph $G$, the zero forcing number of $G$, $Z(G)$, is the smallest cardinality of any set $S$ of vertices on which repeated applications of the forcing rule (described below) results in all vertices being in $S$. The forcing rule is as follows: if a vertex $v$ is in $S$, and exactly one neighbor $u$ of $v$ is not in $S$, then $u$ is added to $S$ in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. The zero forcing number is used to study the maximum nullity/minimum …

Counting Rotational Subsets Of The Circle $\Mathbb{R}/ \Mathbb{Z}$ Under The Angle-Multiplying Map $T\Mapsto Dt$, Ian Tan

Rose-Hulman Undergraduate Mathematics Journal

A rotational set is a finite subset $A$ of the unit circle $\mathbb{R}/ \mathbb{Z}$ such that the angle-multiplying map $\sigma_{d}:t\mapsto dt$ maps $A$ onto itself by a cyclic permutation of its elements. Each rotational set has a geometric rotation number $p/q$. Lisa Goldberg introduced these sets to study the dynamics of complex polynomial maps. In this paper, we provide a necessary and sufficient condition for a set to be $\sigma_{d}$-rotational with rotation number $p/q$. As applications of our condition, we recover two classical results and enumerate $\sigma_d$-rotational sets with rotation number $p/q$ that consist of a given number of orbits.

Impartial Geodetic Building Games On Graphs, Bret J. Benesh, Dana C. Ernst, Marie Meyer, Sarah K. Salmon, Nándor Sieben

Mathematics Faculty Publications

A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the set. The convex hull of a set of vertices is the smallest convex set containing the set. We study variations of two games introduced by Buckley and Harary, where two players take turns selecting previously-unselected vertices of a graph until the convex hull of the jointly-selected vertices becomes too large. The last player to move is the winner. The achievement game ends when the convex hull contains every vertex. In the avoidance game, the …

A Numerical Method For Coefficient Reconstruction Of A Periodic Inverse Source Problem, Robert Ireri

Theses, Dissertations and Capstones

This thesis investigates a numerical method for solving the periodic inverse source problem governed by the Helmholtz equation. The problem involves reconstructing an unknown periodic source term from boundary measurements, which is inherently ill-posed. To address this challenge, we employ a quasi-reversibility method (QRM) combined with a basis function expansion to stabilize the inverse reconstruction. The forward problem is solved using the Lippmann-Schwinger equation, discretized via the trapezoidal rule, and the inverse problem is formulated as a constrained least-squares minimization. The discretized system is efficiently solved using sparse matrix techniques and regularization strategies. Numerical experiments demonstrate the robustness of the …

Discrete Fractional Gompertz Models, Rebecca Oduro

Theses, Dissertations and Capstones

This thesis explores the theory and application of discrete fractional Gompertz models—systems that integrate fractional difference operators into the classical Gompertz growth paradigm. By doing so, these models capture both discrete time steps and the long-range memory effects characteristic of fractional calculus. After outlining the fundamental notions of discrete calculus, discrete fractional sums and differences, and related special functions such as the discrete Mittag–Leffler function, we derive various fractional Gompertz-type equations. We prove the existence and uniqueness of solutions to these fractional difference equations, often employing discrete analogues of standard solution methods like variation of constants. We also investigate 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.

Random Graph Models For Dual Graphs, Anne Friedman

Scripps Senior Theses

This paper aims to better characterize dual graphs derived from state districting maps by developing random graph models that replicate their structural properties. Dual graphs provide a simplified way to represent districting maps, making it computationally feasible to analyze their structure. These representations enable researchers, legislators, and courts to assess district compactness, detect signs of gerrymandering, and generate alternative districting plans. A deeper understanding of the structural patterns of these dual graphs can help researchers choose or design more effective algorithms for redistricting analysis. The random graph models developed in this study serve as testbeds for evaluating algorithmic approaches to …

Empirical Analysis Of Political Districting Splitability Via Uniform Spanning Trees In Polynomial Time, Brooke C. Feinberg

Scripps Senior Theses

This work expands a recently proven conjecture that a polynomial fraction of all uniform spanning trees (USTs) are splittable into k balanced partitions on grid graphs to real-world political districting plans. We investigate whether similar structural properties hold for the planar dual graphs of U.S. counties (cnty) and tracts (t), using Wilson’s algorithm to generate uniform random spanning trees and Breadth- First Search (BFS) to check for splitability into balanced partitions. Our empirical findings suggest that real-world districting plans can be split into 2-balanced, connected partitions in a fraction of polynomial time. This result highlights the potential for scalable redistricting …

Orientable Quadrilateral Embeddings Of Cartesian Products Of Graphs, Matthew Farnsworth, Max Goskie, Adrian Volpe, Jackson Sayre

SPARK Symposium Presentations

In the spirit of Pisanski (1989) we consider orientable quadrilateral embeddings of Cartesian products of cycles on surfaces. We offer a constructive example of such an embedding of three low-order cycles. Then we show more generally that such embeddings exist for the product of a 2-cycle, and even cycle, and an arbitrary third cycle. We represent our graphs using rotation schemes to show this existence. Use of rotation schemes led to the ultimate characterization of our findings visually, providing conjectures for generalizations of products of three cycles.

Two Network Flow Problems: Volume Inequalities For Flow Polytopes Of Full Directed Acyclic Graphs; Optimal Additions To The Low-Stress Bike Network In Lexington, Kentucky, James F. Mcelroy

Theses and Dissertations--Mathematics

This dissertation addresses two distinct problems related by their foundation in network flows. The first problem concerns volumes of flow polytopes of directed acyclic graphs with out-degree sequence (3,2,...,2,0). It is proved that there is an interchange operation on the edge set of these graphs that induces a partial order on the graphs isomorphic to a Boolean algebra, and that moving up through this partial order decreases (weakly) the volumes of the corresponding flow polytopes. This result is reinterpreted in the context of linear extensions for posets that are bipartite non-crossing trees.

The second problem develops a discrete optimization model …

Measuring The Similarity Between Trees Of Different Order, Camilo Morales

HMC Senior Theses

Graphs encode relationships between data. However, due to their versatility, it is often difficult to generalize the notion of similarity between two graphs using a distance function. Since graphs can represent various data sets, specific distance metrics need to be tailored for questions we are interested in answering or the data set we are working with. This project is motivated by ongoing investigations into the evolution of female gender representation in mathematics. By building off previous work that has taken data from the Mathematics Genealogy Project and modeled this evolution of representation via a tree, we would like to develop …

On Linear Invariants Of Hypergraphs, Clara Chaplin

Honors Theses

We introduce linear invariants of hypergraphs as a way to study hypergraphs by their tensor representations. Our primary research goal is to determine what information linear invariants capture about the hypergraphs they arise from. We first investigate the centroid, which is shown to determine the connected components of a hypergraph. Next, we study the derivations of a hypergraph, and use this linear invariant to define a quotient operator $Q_\mathrm{Der}$ on the collection of all hypergraphs. This operator is shown to be a closure operator in that $Q_\mathrm{Der}(Q_\mathrm{Der}(\mathcal{H}))=Q_\mathrm{Der}(\mathcal{H})$ for any hypergraph $\mathcal{H}$. We apply the operator $Q_\mathrm{Der}$ to synthetically generated hypergraphs, …

Schaper Numbers, Palindrome Partitions, And Symmetric Functions, With Applications To Characters Of The Symmetric Group, Karlee J. Westrem

Dissertations, Master's Theses and Master's Reports

Finding the decomposition numbers for the symmetric group is a difficult problem and has led to many different research directions. For a given Specht module, the Schaper sum formula can be refined with knowledge of the Schaper number for the particular partition to give more precise information about the decomposition numbers. In Chapter 2, we give a combinatorial formula for the Schaper number when the partition has at most two columns. At the end, we provide a conjecture for the Schaper number for the partition of shaper (3^n).

Chapter 3 covers the joint work with my advisor, David Hemmer, and …

The Combinatorics Of Integer Partitions Enumerated By Some Exotic Weights, Hunter Waldron

Dissertations, Master's Theses and Master's Reports

Identities of integer partitions generally state that two dissimilar appearing families of partitions are in fact equinumerous when both are restricted to any fixed size. Euler's theorem is a classic example of such an identity, which equates the number of partitions with odd parts to the number of partitions with distinct parts. Lately, analogs of known partition identities involving weights other than size have begun to attract research interest. This dissertation is an investigation of two such weights. In Chapter 2, we study Schmidt weights, which count only parts with indices belonging to some given subset of the positive integers. …

Moore Graphs, Trevor Saxton

Williams Honors College, Honors Research Projects

A Moore graph is a simple regular graph, with n vertices, degree d, and diameter k, that satisfies the Moore bound: n = 1 + d (d − 1)k − 1 d − 2 . There are graphs for which the bound is met and in which existence and uniqueness are known. For k = 2 it is known that the Moore bound is achieved for d = 2, 3, 7, with the case of d = 57 conjectured to exist. For k = 3 the bound is achieved for only d = 3 [5]. Due to the construction of …

On The Combinatorial Invariance For Kazhdan-Lusztig Polynomials, Grover C. Harrell Iii

College of Graduate Studies: Theses & Dissertations

This thesis will be a discussion on the Combinatorial Invariance Conjecture for Kazhdan Lusztig polynomials. The conjecture is widely suspected to be true; and there is an abun dance of computational evidence which supports it. Despite this, no complete proof has been discovered for more than forty years. We will explore some known results about the CIC, particularly those by Dyer, Incitti, Brenti, Caselli, and Marietti.

Apex Graphs And Cographs, Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky

Theory & Applications of Graphs

A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result.

The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a …

(R2096) Pbib-Designs Associated With Products Of Graphs, Medha Itagi Huilgol, Vidya M.D

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we introduce a design, called “geodetic-design" arising from geodetic sets in a graph. A geodetic-design, over a regular graph is an ordered pair D = (V, B), where V = V (G) and B, the set of all geodetic sets, called blocks, containing vertices belonging to geodetic sets, such that every pair of non-adjacent vertices appears in exactly µ blocks. We first find governing results of a geodetic-design, if it exists, and then get such PBIB-designs for different products of graphs. It is common to have geodetic sets of graphs to be independent sets, hence we extend …

Computational Representation, Analysis And Verification Of Requirements In Engineering Design And Systems Engineering, Chandan Kumar Sahu

All Dissertations

Systems are developed to satisfy a set of requirements derived from stakeholders’ needs, defining the problem space for which the system is created as a feasible solution. The system design process begins with eliciting these requirements and concludes with validating whether the created system meets them. Requirements engineering (RE) encompasses elicitation, representation, analysis, documentation, verification, and validation. However, challenges in RE, such as imprecision in natural language (NL), proprietary restrictions, and a lack of standardized quality metrics, hinder the creation of well-formed and comprehensive requirements. These challenges complicate formalization and analysis of requirements.

This dissertation addresses these challenges by proposing …

A Dynamical Systems Approach For Modeling Malware Propagating Through A Network And Potential Solutions Towards Mitigating Spread, James Johnson

Cybersecurity Undergraduate Research Showcase

Many people draw close parallels between malware propagating through a network and an epidemic spreading through a population. Epidemics are often modeled by a Susceptible-Infected-Recovered (SIR) model, in which a similar system of equations can model the spread of a virus through a computer network, and can be simplified when making assumptions about the network itself and its fixed number of nodes and edges. In this instance, malware propagating in a network also should reflect the network it is propagating through, in which the dynamical system will factor in the nodes of the network and their properties. The system itself …