Discrete Mathematics and Combinatorics Commons^™

Exploring The Metric Dimension Of The Graph Representing A Four-Ring Polycyclic Aromatic Hydrocarbon: Interstellar 1-Cyanopyrene, Andrei Matthew V. Robino, Sebastian Alex C. Traviña, Karl Benedict P. Narag, Mark Anthony B. Casao, Helix Raven C. Llanes, Azriel C. Alejo, Jonel C. Celamor

Sinaya: A Philippine Journal for Senior High School Teachers and Students

A graph's metric dimension is a parameter that denotes the minimum possible number of vertices in a subset that gives each vertex in the graph a unique representation. Despite extensive research on the metric dimension of polycyclic aromatic hydrocarbons (PAHs), there is currently no focused analysis on the metric basis and metric dimension of 1-cyanopyrene. In chemistry, graphs can be used to depict molecular structures. In this study, graph theory, specifically the concept of metric dimensions, is applied to the molecular structure of 1-cyanopyrene, which was detected in space for the first time in 2024. 1-cyanopyrene is a molecule made …

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 …

A Leslie System For A Demographic Simulation: From An Actuarial Point Of View, David Kings

Electronic Theses and Dissertations

This thesis develops a discrete stochastic linear systems interpretation of age–stage demographic evolution grounded in Leslie operators and realized in a discrete-event simulation implemented with salabim. The central claim is that one annual cycle of the simulation constitutes a cone-preserving, stochastic affine transformation on a high- dimensional population state vector indexed by age, sex, marital status, household type, employment, and education, and that the composition of yearly operators yields a random matrix product whose top Lyapunov exponent is the stochastic counterpart of the Perron–Frobenius growth rate (Caswell, 2001; Tuljapurkar, 1997)[1, 2]. The actuarial bridge is constructed by mapping simulated survival …

An Income Subsystem As A Discrete Stochastic Leslie System: A Simulation-Based Approach, Fahd Nii Okantah Cobblah

Electronic Theses and Dissertations

This thesis formulates the household-income engine of an integrated population sim- ulator as a Discrete Stochastic Leslie System (DSLS). The nonnegative state vector nt ∈ Rk + aggregates income, savings, debt, employment, and transfers. (Here, the subscript + denotes the positive cone, i.e., vectors with nonnegative components). Annual evolution is linear in state, stochastic in coefficients: nt+1 = Ttnt + εt, with Tt : Rk + → Rk + cone-preserving. Exogenous macro drivers (inflation, employment, tax, salary inflation, mortgage) are forecast via ARIMA; forecasts multiply entries of Tt, preserving linearity in expectation while introducing realistic temporal correlation. The discrete-event implemented …

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 …

Modeling The Probability Of N Clonal Rosettes In A Bromeliaceae Genetic Individual, Erin N. Bodine, Layla K. Lammers

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Forbidden Triples For $2$-Connected Graphs With Minimum Degree Three Which Contain $K_4$ And $K_{2,2}$, Takafumi Kotani, Yoshimi Egawa

Theory & Applications of Graphs

For a family $\mathcal{H}$ of graphs, a graph $G$ is said to be $\mathcal{H}$-free if $G$ contains no member of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{G}_2^{(3)}}(\mathcal{H})$ denote the family of $2$-connected $\mathcal{H}$-free graphs having minimum degree at least $3$. This paper is concerned with families $\mathcal{H}$ of connected graphs with $|\mathcal{H}| = 3$ such that $\mathcal{G}_2^{(3)}}(\mathcal{H})$ is a finite family. In particular, we show that for a connected graph $T$ of order at least $3$ that is not a star, $\mathcal{G}_2^{(3)}(\{K_4,K_{2,2},T\})$ is finite if and only if $T$ is a path of order at most $6$.

Star-Critical Weakened Ramsey Numbers, Mark R. Budden, Monu Moun, Jagjeet Jakhar

Theory & Applications of Graphs

The weakened Ramsey number $r^{s,t}(G)$ is defined to be the least $p\in \mathbb{N}$ such that every $t$-coloring of the edges of the complete graph $K_p$ contains a subgraph isomorphic to $G$ that is spanned by edges that use at most $s$ colors ($1\le s\le t-1$). The star-critical weakened Ramsey number $r^{s,t}_*(G)$ then determines the minimum number of edges that must join a vertex to $K_{r^{s,t}(G)-1}$ in order for this Ramsey property to hold. We begin by showing that $r_*^{s,t}(K_n)=r^{s,t}(K_n)-1$ for all $n\in \mathbb{N}$. Then, building off of Khamseh and Omidi's recent determination of $r^{s,t}(K_{1,n})$ when $s=t-1$ and $s=t-2$, we focus …

Packing Independent Cliques Into Planar Graphs, Csaba Biró, Gabriel Collado, Oscar Zamora

Theory & Applications of Graphs

The indeque number of a graph is largest set of vertices that induce an independent set of cliques. We study the extremal value of this parameter for the class and subclasses of planar graphs, most notably for forests and graphs of pathwidth at most $2$.

Incremental Increases Between Successive Integers When Raised To The Nth Power, Sutton J. Olesen

Rose-Hulman Undergraduate Mathematics Journal

For thousands of years, the beautiful field of number theory has captivated mathematicians with its elegant simplicity. Positive integers continue to reveal properties and relationships that are a joy to uncover, and in this paper, we investigate a pattern involving exponents and factorials while exploring some common notations in the field of number theory. Combinatorics, the field dealing with the mathematics of counting and arranging, also holds a presence in this paper. Pascal’s Triangle–the foundation of binomial expressions, also comes into play due to its tight relationship with combinatorics. Pascal’s Identity, the property that builds the triangle, becomes very useful …

Corrigendum To "Face-Magic Labelings Of Polygonal Graphs", Wai Chee Shiu, Richard M. Low, Andy K. Liu

Theory & Applications of Graphs

In this note, we correct a misstatement of a theorem.

Degeneracies Of Triangulated Graphs, Allan Bickle

Theory & Applications of Graphs

A graph $G$ is $k$-degenerate if each subgraph has minimum degree

at most $k$. The degeneracy\textbf{ }$D\left(G\right)$ is the smallest

$k$ such that $G$ is $k$-degenerate. We determine the truth values

of four statements (using different quantifiers) about when a planar

graph $G$ with degeneracy $k$ has a triangulation with degeneracy

$l$. We characterize which 3-connected planar graphs can only be

triangulated to degeneracy 3. Then we consider analogous questions

for maximal planar bipartite graphs. We prove some structural results

on these graphs, including results on decomposition of planar graphs

into various types of bipartite graphs.

Numerical Results Of New And Modified Heuristics For The Vertex Coloring Problem, Elliot Hanson

Summer Research Showcase

The chromatic number, χ(G) of an undirected graph G=(V,E) is the minimum number of colors required to color its vertices so that no two adjacent vertices have the same color. Given a graph, G, finding its chromatic number is useful for solving scheduling problems and other combinatorial optimization problems. However, determining the chromatic number of a connected graph is NP-Hard, meaning there is no known polynomial time algorithm which solves it. Thus, we are interested in heuristic solutions which give approximations for the chromatic number in polynomial time. There are well-known heuristics for finding χ(G) for any graph G. …

Skolem Number Of Kagome Lattice Graphs, Braxton Carrigan, Max Martone

Theory & Applications of Graphs

A proper Skolem labelling of a graph $G$ is a function assigning a positive integer to each vertex of $G$ such that any two vertices assigned the same integer are that distance apart in the graph. The Skolem number of a graph is smallest number $n$ such that there exists a proper Skolem labelling only using the positive integers less than or equal to $n$. In this paper, we will begin by proving the Skolem number for another family of subgraphs of the hexagonal lattice and then prove the Skolem number for two families of subgraphs of the Kagome Lattice.

Multiple Monochromatic Subgraphs In Edge-Colored Graphs, Emma Felicity Jent

Dissertations

Ramsey theory, though a relatively young branch of mathematics, has captivated the attention of graph theorists, combinatorialists, and theoretical computer scientists alike through its raw beauty, versatility, and powerful applications. Before it emerged as a branch of mathematics, the central idea of Ramsey theory appeared in the form of three lemmas in three separate papers by three different mathematicians working on three distinct areas of research. The first such lemma was published by David Hilbert in 1892, followed by the second lemma published by Issai Schur in 1916. However, Frank Ramsey’s renowned lemma, published in 1930, compelled mathematicians to establish …

Homomesies And Toggleability Spaces, Alec Mertin

All Dissertations

We study the homomesy phenomenon under the rowmotion operator acting on order ideals of posets. We provide details for the extensions of several results in the literature concerning homomesies of toggleability statistics from finite to infinite orbits, which allows us to obtain homomesies for piecewise-linear and birational rowmotion, even in the case of infinite orbits. Integral to this is a novel generalization of a result in the literature, which relaxes the conditions needed to lift a statistic.

We completely describe the order ideal (resp. antichain) toggleability space for general fences: the space of statistics which are linear combinations of …

Simplicial Decomposition And Realization, Matthew Ellison

Dartmouth College Ph.D Dissertations

In simplicial decomposition, we define two invariants --- V_Z and V_Q --- which represent notions of integral and rational volume of a certain class of simplicial complexes. We prove V_Z and V_Q are additive under disjoint union and connected sum, and investigate `integrality gaps' between the two quantities. We apply the theory to establish a conjecture of Sleator, Thurston, and Tarjan on tetrahedral fillings, and, as a corollary, obtain a new proof of Pournin's 2012 result on the diameter of the associahedron. In simplicial realization, we provide practical sufficient conditions and computer code to prove the existence of Euclidean embeddings …

The Degrees Of The Irreducible Representations Of The Symmetric Group With Respect To Primes, Vanessa F. Beeler

Master's Theses

In this thesis, we explore the relationship between the degrees of irreducible matrix representations of the symmetric group and prime numbers. We start by building up the required background necessary to construct our results. We dive into topics of discrete mathematics including matrix representations, characters of representations, integer partitions, conjugacy classes, class functions, and tableaux. Some other key ingredients in our work include using character tables to classify the irreducible rep- resentations of the symmetric group and the hook-length formula to easily compute the degrees of these representations. Once we have laid the groundwork for our in- vestigation, we begin …

On The Design Of A Framework For Large-Scale Exploratory Graph Analytics, Oliver Andres Alvarado Rodriguez

Dissertations

Large-scale exploratory graph analytics merges data science with high-performance computing to extract critical insights from network-representable data. Data scientists routinely analyze data from the natural, social, and computing sciences by representing it as networks, or graphs, where objects become vertices and their relationships become edges. This representation allows data scientists to add graph analytics to their toolbox. However, designing tools for large-scale exploratory graph analytics is challenging due to the complexities of graph algorithms, such as high communication in distributed systems and large memory demands. These challenges can lead to overly complex software, which limits usability and development to a …

Lower Bounds For The Total Distance $K$-Domination Number Of A Graph, Randy R. Davila

Theory & Applications of Graphs

For $k \geq 1$ and a graph $G$ without isolated vertices, a \emph{total distance $k$-dominating set} of $G$ is a set of vertices $S \subseteq V(G)$ such that every vertex in $G$ is within distance $k$ to some vertex of $S$ other than itself. The \emph{total distance $k$-domination number} of $G$ is the minimum cardinality of a total $k$-dominating set in $G$ and is denoted by $\gamma_{k}^t(G)$. When $k=1$, the total $k$-domination number reduces to the \emph{total domination number}, written $\gamma_t(G)$; that is, $\gamma_t(G) = \gamma_{1}^t(G)$. This paper shows that several known lower bounds on the total domination number generalize …

The Integer-Antimagic Spectra Of A Weak Join Of Hamiltonian Graphs, Ugur Odabasi, Dan Roberts, Richard M. Low

Theory & Applications of Graphs

A simple graph $G$ with vertex set $V(G)$ and edge set $E(G)$ is \emph{$\mathbb{Z}_{k}$-antimagic} if there exists a function $f: E(G) \to \mathbb{Z}_{k} \backslash \{0\}$ such that the induced function $f^+(v)=\sum_{uv\in E(G)} f(uv)$ is injective. The \textit{integer-antimagic spectrum} of a graph $G$ is the set IAM$(G) = \{k: G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}$. A \emph{weak join} of vertex-disjoint graphs is the collection of the graphs with additional simple edges (possibly none) between the original graphs. In this paper, we characterize IAM$(H)$ where $H$ is a weak join of Hamiltonian graphs.

Prime Labelings On A 3xn Grid Graph, Stephen J. Curran, Matt A. Ollis

Theory & Applications of Graphs

It is conjectured that the mxn grid graph has a prime labeling for all positive integers m and n. It is known that for any prime p and any integer n such that 1≤n≤p², there exists a prime labeling on the pxn grid graph P_m x P_n. Also, it is known that the ladder P₂ x P_n has a prime labeling for all positive integers n. We assume that Goldbach's Even Conjecture and a strengthened variant of Lemoine's Conjecture are true in order to show that the 3xn grid graph P …

All Graphs Of Order N With Distinguishing Number N−1 Or N − 2, Andi Pujo Rahadi, Edy Tri Baskoro, Suhadi Wido Saputro

Theory & Applications of Graphs

Let G be a simple connected graph. The distinguishing number of G, denoted by D(G), is the least integer d such that G has a vertex d-labeling preserved only by the trivial automorphism. In this paper, we characterize all graphs of order n with distinguishing number n − 1, or n − 2.

On The Hexgame, Corwin Jones

Mathematical Sciences Technical Reports (MSTR)

The SOMA Cube has been studied by mathematicians for a number of decades, but so far methods for solving three-dimensional space-filling puzzles like the SOMA cube remain numerical; we do not have a means to predict the number of solutions to SOMA-like puzzles. We present a two-dimensional puzzle that shares certain features of the SOMA Cube, with the hope that it will be a more convenient object of study for future research into space-filling/space-covering puzzles.

Two-Player Trick-Taking Games On Bipartite Tournaments., Allan Bagley

College of Arts & Sciences Senior Theses

We consider a two-person game played on a bipartite tournament with equal size parts. The game is modeled after trick-taking card games like bridge or euchre. The two players, South and North, each receive one of the parts as their hand, and the arcs from a vertex in one hand beat the corresponding vertices in the other hand. The game is played over rounds called tricks where the number of tricks is equal to the number of vertices in each player’s hand. At the beginning of the game, one player is designated as the leader, and they play the first …

Maximal Independent Set Algorithms Within Procedural Planar Maps: A Large-Scale Evaluation, Chaucer Ihrig

Honors College Theses

Analysis of a childhood game has led us to the problem of maximum independent sets in planar graphs. We wrote a graph creation utility using R to generate a random planar map and its dual graph. This utility then finds a graph’s maximal independent set using a variety of six algorithms. We investigate statistical connections between graph structure, colorability, and the maximal independent sets found using these algorithms over an incredibly large and procedurally generated dataset. We find one can always win the coloring game if the resultant graph is two-colorable. The algorithms perform statistically and practically significantly better on …

Knighted Pawn's Tour, Morgan Wilson

Honors Theses

The Knighted Pawn’s Tour is a variant of the traditional Knight’s Tour problem, whichitself is an instance of the Hamiltonian cycle problem. The deviation from the Knight’s Tour problem is that a pawn begins on any field on the second rank (row), and advances with legal moves that can include captures to the opposite end of the board to become a knight. These fields, used by the pawn on the path to knighthood, are subsequently forbidden for the knight’s return to the starting field. The knight must traverse the rest of the chessboard, visiting each remaining field exactly once …

Combinatorial Rigidity And Flexibility Of Simplicial 2-Complexes With Few Vertices, Serge A. Lawrence, Abdulkarim M. Magomedov, Olga I. Chelyapina, Valentina M. Rudenko

Theory & Applications of Graphs

We study the problem of reconstruction of a simplicial 2-complex from its 1- skeleton together with the prescribed quantities of 2-simplices at each 1-simplex, under the restriction that these quantities are bounded above by 2. It is a known fact that a 2-complex is uniquely reconstructible, or “combinatorially rigid”, if it has 5 or fewer vertices. In this paper “combinatorially flexible” 2-complexes (that is, non-uniquely reconstructible from their 1-skeletons) with 6 vertices are characterized in terms of necessary 2-subcomplexes.

Counting Hamiltonian Cycles In Quartic Circulant Graphs, Allison Hilliard

Seaver College Research And Scholarly Achievement Symposium

We consider the problem of counting Hamiltonian cycles in circulant graphs $C_n^{1,k}$. Our method is to partition the set of Hamiltonian cycles according to their winding numbers. Then, we construct a weighted digraph that allows us to produce a generating function that counts the number of Hamiltonian cycles for each winding number. Summing these generating functions derives a formula for the total number of Hamiltonian cycles in a circulant graph with $n$ vertices.

32 - Nested Two Level Decomposition For Quantum Computing, Andrew Maciejunes, John Stenger, Dan Gunlycke, Nikos Chrisochoides

Undergraduate Research Symposium

Abstract—We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm (QAOA). A Problem-Level Decomposition (PLD) partitions a 9-node (72-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further simplified via Circuit-Level Decomposition (CLD), enabling execution on near-term quantum devices. Our approach achieves up to 90% reductions in circuit depth and qubit count. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.