Discrete Mathematics and Combinatorics Commons^™

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^K_n$ where $n$ is the number of vertices and $K$ is a set containing elements that correspond to the allowed edges in the circulant graphs. After sorting the cycles by a topological invariant called the winding number, we use a modified transfer matrix method to convert local data into global structures. The result is a generating function that counts the number of Hamiltonian cycles in a circulant graph with $n$ vertices. The results for $K=\{1,2\}$ and $K=\{1,3\}$ have been found by previous authors. We focus on the case where …

Irreversible K-Threshold Dynamics On Corona And Base-B Corona Product Graphs, Eric J. Moon, Soumya Bhoumik, Paul Flesher

SACAD: Scholarly Activities

This poster studies the irreversible k-threshold process on corona-type graph products, where a vertex becomes colored once at least k of its neighbors are colored and then remains colored permanently. We focus on corona, double corona, and base-b corona product graphs built from cycles and complete graphs, with particular attention to how graph structure affects complete activation from a minimum seed set.

A generalized reduction lemma is used to relate threshold dynamics on layered corona graphs to smaller residual graphs, yielding explicit formulas for the irreversible k-threshold conversion number on both corona and double corona families. The …

Extremal Connectivity In Graphs And Matroids, Yiwei Ge

LSU Doctoral Dissertations

Connectivity is a central theme in both graph theory and matroid theory. This dissertation investigates extremal connectivity in graphs and matroids, with emphasis on unavoidable structures and minimal connectivity phenomena.

Chapter 2 introduces cycle-contraction minors of graphs and investigates their structural properties. We establish a connection between cc-minors and induced subgraphs via graph duality. The main result gives an unavoidable-families characterization for cc-minors of sufficiently large loopless $2$-connected graphs.

Chapter 3 studies super-minimally $3$-connected graphs, namely $3$-connected graphs that have no proper $3$-connected subgraphs. We establish extremal bounds on structural parameters of these graphs, including the minimum number of degree-$3$ …

A 4-Dimensional Rubik’S Cube You Can Hold: How It’S Possible And The Math Behind It, Eric J. Moon

SACAD: Scholarly Activities

This poster examines the physical 2x2x2x2, a hand-held realization of a 4-dimensional Rubik’s Cube invented by Melinda Green. Unlike most higher-dimensional twisty puzzles, which exist only as software simulations, this puzzle provides a physical model for exploring 4-dimensional rotation, symmetry, and solving methods. The poster introduces the structure of the puzzle, its canonical move system, and several algebraic ideas that help explain how scrambling and solving work.

From a mathematical perspective, the puzzle can be studied using group actions, commutators, conjugation, and combinatorial counting. In particular, the number of reachable states depends on corner permutations, corner orientations, parity restrictions, twist …

Circuits And Enumeration Problems For Matroids, Christine H. Cho

LSU Doctoral Dissertations

This dissertation is a collection of work concerning the structure and enumeration of circuits and other distinguished sets in a matroid. The Tutte polynomial, recognized as the universal deletion-contraction invariant in matroid and graph theory, is a natural starting point when considering enumeration problems for matroids. The main result in Chapter 2 generalizes a theorem of Dean Lucas concerning the Tutte polynomial and its behavior under rank-preserving weak maps. This generalization provides an avenue for comparing the numbers of circuits, bases, rank-k flats, and hyperplanes of a matroid containing an element given two distinct, yet related, elements.

Chapter 3 addresses …

Algorithm Performance In The Search For Hamiltonian Cycles, Chance Davis

Honors Theses

The Hamiltonian cycle problem is ubiquitous in both computer science and graph theory: Given a connected graph, a solution would either confirm the existence of a cycle which visits each vertex only once or its nonexistence. The importance of this problem, as well as its difficulty, is described in the Clay Mathematics Institute’s Millenium Prize Problems and Karp’s 21 NP-complete problems. Despite its “hardness,” solutions to the Hamiltonian cycle problem are desired in logistics, electronic circuit design, and network routing, among other fields. In this work, we benchmark a promising exhaustive enumeration algorithm on various graphs, including ones derived from …

On The Extreme Complexity Of Certain Nearly Regular Graphs, Gregory P. Constantine, Gregory C. Magda

Theory & Applications of Graphs

The complexity of a graph is the number of its labeled spanning trees. It is demonstrated that the seven known triangle-free strongly regular graphs are graphs of maximal complexity among all graphs of the same order and degree; their complements are shown to be of minimal complexity. A generalization to nearly regular graphs with two distinct eigenvalues of the Laplacian is presented. Conjectures and applications of these results to biological problems on neuronal activity are described.

Cycle-Based Characterizations Of The Cycle Completable Graphs, Terry A. Mckee

Theory & Applications of Graphs

Cycle completable graphs were originally defined to answer matrix completion problems and have since received diverse graph-theoretic descriptions, in spite of not directly mentioning cycles. This paper characterizes such graphs by their chordless cycles never having ``bridges'' (as defined in H.-J. Voss's 1991 monograph {\em Cycles and Bridges in Graphs\/}) that have more than two vertices of attachment in the cycle. This approach is then related to the well-studied, yet seemingly quite distinct, classes of chordal graphs and series-parallel graphs. This is done by allowing chords to be ``bridges'' that have exactly two vertices of attachment.

Forbidden Induced Restrictions And Unavoidable Minors In Matroids, Matthew P. Mizell

LSU Doctoral Dissertations

Targets are matroids that arise from a nested sequence of flats in a projective geometry. This class of matroids was introduced by Nelson and Nomoto, who found the forbidden induced restrictions for binary targets. In this dissertation, their result is generalized to targets arising from projective geometries over $GF(q)$. In addition, targets arising from nested sequences of affine flats are introduced and the forbidden induced restrictions for these affine targets are determined.

In 1963, Halin and Jung proved that every simple graph with minimum degree at least four has $K_5$ or $K_{2,2,2}$ as a minor. Mills and Turner proved an …

(Si16-07) Computing The Kirchhoff Index And The Wiener Index Of Spiro Para Hexagonal Cylinder Chain, Md Selim Reja, Sk. Md. Abu Nayeem

Applications and Applied Mathematics: An International Journal (AAM)

In graph theory, the Kirchhoff index serves as a metric to evaluate the complexity of a graph. It is determined by adding up the resistance distances between every pair of vertices in the graph. In a network created from the given graph by substituting each edge by a unit resistor, the resistance distance between a pair of specified vertices is equivalent to the electrical resistance between them in the constructed network. Basically, it measures the convenience with which data or flow can move between various locations in a network that the graph represents. In terms of graph matrices, the Kirchhoff …

Demystifying Hardware Formal Verification For Undergraduate Education: A Risc-V Processor Case Study With Coursework Implementation, Riley A. Peters

Master's Theses

Hardware verification engineers apply formal methods to prove that a digital device always behaves according to its specification. This differs from traditional functional verification, in which engineers establish correctness by repeatedly sending test inputs to the device and comparing the outputs against a reference model. With the growing complexity of integrated circuits, the demand for digital verification engineers with formal methods experience has continued to increase. However, California Polytechnic State University: San Luis Obispo's current curriculum lacks dedicated material to prepare students for these roles.

This thesis seeks to address the lack of formal methods material through two efforts. First, …

Enumerating Matrices Of A Given Order Over Finite Fields, Thor Richard Gabrielsen

Honors Theses

This thesis derives a generating function that describes the matrices of a given multiplicative order over finite fields of a given order assuming that the order of a field is not a divisor of the desired order of the matrix. This is done by using the power series known as the cycle index derived from the rational canonical form. This index can be factored, and using the fact that the minimal polynomial divides some polynomial of the form x^k − 1 we can show that the minimal polynomial is squarefree. This sufficiently restricts the form of the rational canonical form …

An Introduction To Modern Conversations On Knot Invariants, Stella Shah

Scripps Senior Theses

Knot Theory is a vast and diverse subfield of modern mathematics involving the classification and abstraction of knots and links. In this thesis, we wish to provide the necessary background for and an explanation of two papers in different subfields of knot theory, The Forbidden Quiver of a Link, and Biquandle Fares and Link Invariants.

In Chapter I, we begin with an introduction to knot theory and knot invariants. We continue to present the example of Fox Colorings, and conclude the chapter with an example of the Fox Coloring Number Invariant.

In Chapter II, we explore the derivation and utilization …

Balanced Multi-Party Tournament Designs, Parsa Nematollahe

Honors College Theses

This paper introduces Multi-Party Tournament (MPT) designs that generalize established combinatorial structures, including Whist, Pitch, and Generalized Whist tournament designs. This work will formally define MPTs, establish the fundamental properties of resolvability, fullness, and balance, and formulate a mathematical and algorithmic foundation for multi-party tournament scheduling. The primary contributions of this research are the presentation of necessary and sufficient existence conditions for MPTs across various properties and parameters, the identification of connections between MPTs and other fields of mathematics such as combinatorial design theory, graph theory, and probability theory, and the investigation of MPT construction algorithms, including tree-search, finite-field constructions, …

Extensions Between Modules Defined By Lattice Paths In The Preprojective Algebra, Chloe Napier

Theses and Dissertations--Mathematics

In 2001, Fomin and Zelevinsky introduced cluster algebras which appear as coordinate rings of many varieties. We study cluster algebras coming from Richardson varieties. Leclerc gives a cluster structure on Richardson varieties using the representation theory of preprojective algebras. While this construction is very algebraic, we take a more combinatorial approach. The main goal is to find a combinatorial description for when certain cluster variables are compatible, or equivalently when modules defined by lattice paths in the preprojective algebra have trivial extensions. We extend the known results from Geiss, Leclerc, and Schröer that answer this question in the case of …

Combinatorial Models For Nonnegativity In Flag Varieties, Williem L. Rizer

Theses and Dissertations--Mathematics

The nonnegative Grassmannian admits a widely studied cell decomposition due to Alexander Postnikov, whose cells are indexed by positroids and modeled by several equivalent combinatorial objects. Subsequent work by authors including Lauren Williams, Suho Oh, and Carolina Benedetti has further developed the combinatorics and geometry of these structures. In this dissertation, we extend some of Postnikov’s combinatorial framework to the nonnegative flag variety. While cell decompositions in this setting were previously obtained, notably in work of Konstanze Rietsch, our focus is on providing new combinatorial models that make this structure more explicit and computationally tractable. We introduce flag positroid pipe …

Catalan And Hyper-Catalan Numbers: Combinatorial Applications To Polynomial Equations, Leilani Natale

Williams Honors College, Honors Research Projects

In this paper, we study Catalan numbers and their generalization, hyper-Catalan numbers, and explore how these sequences arise naturally in the context of solving polynomial equations using infinite power series. We begin by introducing the Catalan numbers through their combinatorial interpretation as triangulations of convex polygons. Using this geometric definition, we derive a relation whose recursive structure leads to a quadratic functional equation. Interpreting this relation as a formal power series equation allows us to express solutions to quadratic equations as infinite power series whose coefficients are given by the Catalan numbers. This framework is then extended by allowing polygon …

Small Antiperfect Steiner Triple Systems, Justin Z. Schroeder, Joshua Ganschow

Research & Publications

The cycle structure of Steiner triple systems (STS) has been well studied with regard to uniform STS and cycle switching. Of particular interest among uniform STS are perfect STS, in which every cycle graph consists of a single cycle. In this paper, we initiate the study of antiperfect STS, in which every cycle graph consists of a union of at least two cycles. We prove that an antiperfect STS(n) exists for all admissible n ≥ 15 and provide a complete listing of all antiperfect STS(n) for n ≤ 19 and all antiperfect STS(21) with a non-trivial automorphism. Furthermore, it is …

Gliders On The Sca Model, Alexa Renner

Mathematical Sciences Technical Reports (MSTR)

The Stranded Cellular Automata (SCA) model consists of a grid of cells which can each contain between zero and two strands apiece and two turning rules that control when strands turn and when they cross. While patterns on this model have been studied previously, such research has not needed an algebraic description of the model. We provide a formal algebraic definition of patterns on the model, define gliders on the model in a way which is semi-compatible with definitions of gliders in other cellular automata models, and classify all 1- and 2-stranded gliders on this model. In addition, we prove …

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 …

Symmetry In Latin Hypercubes, Levi Neiburger

Theses and Dissertations

Let [n] = {1, ..., n}. A hypercube H of order n and dimension d is a d-dimensional array whose nᵈ cells are indexed by [n]ᵈ. A hyperplane in H is obtained by fixing one coordinate, while allowing the remaining d–1 coordinates to vary. We wish to color each cell of H from a palette of n^d-1 colors such that each hyperplane is polychromatic.

Our main result is the following. Let n be sufficiently large. There exists a symmetric coloring of the d-dimensional hypercubes of order n whose all hyperplanes are polychromatic if and only if: …

A New Parsimony-Based Method For Reconstructing Sequences Of Developmental Events And Estimating Rates Of Intraspecific Variation, With Applications To Trilobites, Alexander Benjamin Bradley

Graduate Theses, Dissertations, and Problem Reports (ETD)

Ontogenetic Sequence Analysis (OSA) is a method for reconstructing multiple sequences of abrupt phenotypic transformations (developmental events) for sampled populations of any kind of organism. It makes use of cladistic parsimony software to produce a network, or graph, whose vertices represent unique phenotypes at different stages of maturity (“semaphoronts”) and whose edges describe the developmental events occurring between semaphoronts. It is a powerful tool for constraining the range of developmental variation possible for a given species and generating sample statistics capable of identifying both the most common and the outlier ontogenetic sequences. However, OSA has seen little use since its …

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 …