Discrete Mathematics and Combinatorics Commons^™

On Graphs With Chromatic Number And Maximum Degree Both Equal To Nine, Rachel Galindo, Jessica Mcdonald

Theory & Applications of Graphs

An equivalent version of the Borodin-Kostochka Conjecture, due to Cranston and Rabern, says that any graph with $\chi = \Delta = 9$ contains $K_3 \lor E_6$ as a subgraph. Here we prove several results in support of this conjecture, where vertex-criticality and forbidden substructure conditions get us either close or all the way to containing $K_3 \lor E_6$.

Exact Formulas For Restricted Coprime Representations Of Even Integers, Andres Mauricio Salazar

Communications on Number Theory and Combinatorial Theory

Let p ≥ 5 be prime, and let g(2n,p) denote the number of unordered representations by positive integers 2n = h + k, with h ≤ k and gcd(h,6p) = gcd(k,6p) = 1. Every positive integer coprime to 6 belongs to exactly one of the families 6z + 1 and 6z + 5. In each family, divisibility by p excludes one explicit residue class of z modulo p. We use these two excluded classes to derive an exact formula for g(2n,p) from finite residue counts and nonnegative lift counts. The formula is valid for every positive integer n, including all …

Self-Organized Criticality In Biased Activated Random Walk, Joshua Meisel

Dissertations, Theses, and Capstone Projects

We demonstrate many of the conjectured universality and self-organized criticality (SOC) properties of the interacting particle system Activated Random Walk (ARW) in the setting of one-dimensional biased walks, as formulated for instance in Levine and Silvestri’s 2024 survey. Namely, there exists the same limiting critical state for two finite ARW models, as well as for the infinite model as the density approaches its critical value from below. Many of the desired properties hold, including heavy-tailed avalanches, but spatial correlations decay exponentially fast, a deviation from the SOC paradigm. Nonetheless, the obtained decay rate vanishes with the bias. Since the critical …

Modeling The Clonal Rosette Composition Of A Bromeliaceae Genet: A Combinatorial Approach, Layla K. Lammers, Erin N. Bodine

Spora: A Journal of Biomathematics

Bromeliaceae, a neo-tropical plant family encompassing over 3,000 species, exhibit two modes of reproduction: sexual reproduction via flowers and seeds, and asexual reproduction via genetically identical clonal rosettes. The vegetative bodies of bromeliads form rosettes with new leaves emerging from the center and clonal rosettes emerging above a single leaf in the rosette, resulting in a genetic individual consisting of a seed-grown rosette and multiple iterations of clonal rosettes. This research develops a combinatorial model of probability that a single genetic individual will include at least n clonal rosettes when a single rosette can produce at most 1 or 2 …

Asymptotic Enumeration Of K-Bounded Functions Using Toeplitz Matrices, Tiago Cavalcante Trindade, Pedro Martineli

Rose-Hulman Undergraduate Mathematics Journal

We introduce the concept of $(\alpha, \lambda)$-bounded functions, characterized by limited local variation, which is especially useful in discrete sets. Initially, we formally define these functions and investigate their fundamental properties, highlighting significant differences from continuous functions. The main result obtained is the asymptotic estimate of $a(n, k)$, representing the number of functions from $[n]$ to $[n]$ that are $k$-bounded with respect to the Manhattan distance. The proof of this result combines Toeplitz matrices with a well-known inequality from graph theory.

Underclosed Posets, Richard Ngo

McNair Summer Research Program

Underclosed complexes are a recent generalization of interval graphs to higher dimensions. Motivated by underclosed complexes, we define and study underclosed posets. Order ideals of these posets correspond to pure underclosed complexes. We classify which principal order ideals are rank-symmetric (and in fact are self-dual).

Ramsey Chains In Graphs, Ritabrato Chatterjee

Dissertations

The research in this work deals with decomposition of graphs and Ramsey theory, two popular areas of research in graph theory due to numerous fascinating problems and the sheer mathematical beauty of the subjects. A decomposition {G₁, G₂, ..., G_k} of a graph G into subgraphs of G is ascending if the subgraph G_i is isomorphic to a proper subgraph of G_i+1 for i = 1, 2, ..., k − 1. The well-known and long-standing of Ascending Subgraph Decomposition Conjecture states that every graph has an ascending subgraph …

Waiting For The Magic: A Historical And Mathematical Study Of Queues In Disney Theme Parks, Nina E. Becket

Journal of Humanistic Mathematics

This paper, written as part of an honors research project in high school, provides an introduction to the line and queuing systems at Disney theme parks. We begin with a brief history of Disney World and its creators. We then introduce the basics of queuing theory and queuing notation. Finally, we examine modern line systems at Disney (as of 2023) and the future of its different queue systems.

The Edge-Distinguishing Game, Nathaniel Benjamin, Elisa Benthem, Cooper Burkel, Marissa E. Chesser, Mike Janssen

Communications on Number Theory and Combinatorial Theory

In this paper, we introduce a graph coloring game called the Edge-Distinguishing Game (EDGe). The edge-distinguishing chromatic number of a graph is used to determine the moves each player can make. We determine which player has a winning strategy for particular graphs and graph families. Additionally, utilizing principles from game theory as well as previous work on a computational solution for the Game of Cycles.

(R2139) Italian Domination Number For Some Classes Of Trees, Amritha Prakash, Ragukumar Pandurangan

Applications and Applied Mathematics: An International Journal (AAM)

For a graph G with vertex set V , an Italian dominating function is a function f from V to {0, 1, 2} which has the property that for every vertex which is assigned 0, it must either adjacent to a vertex assigned 2 under f or adjacent to at least two vertices assigned 1 under f. The weight of an Italian dominating function is the sum of all weights assigned to the vertices. The minimum weight of an Italian dominating function f is the Italian domination number. Finding a graph’s Italian domination number is a well-known NP-Complete problem. Even …

(R2175) Application Of Similarity Measures On Bipolar Complex Neutrosophic Matrices In United Nations’ Sdg-17 Using Python, T. Muthuraji, N. Krishnapraveen

Applications and Applied Mathematics: An International Journal (AAM)

The increasing complexity of decision-making environments demands mathematical frameworks capable of modeling bipolar, indeterminate, and phase-dependent uncertainty simultaneously. Bipolar Complex Neutrosophic theory provides such a structure, but the extension of similarity measures to matrix-based environments remains largely unexplored. In this study, we formally develop cosine, Dice, Jaccard, and hybrid vector similarity measures for Bipolar Complex Neutrosophic Matrices (BCNMs). Each matrix element is represented by a Bipolar Complex Neutrosophic Number (BCNN), enabling structured representation of multidimensional uncertainty within a matrix framework. We also design and implement efficient Python-based computational tools to automate similarity evaluation for BCNMs. The proposed algorithms reduce computational …

(R2185) Operations On Bipolar Complex Neutrosophic Matrices And Its Application In Un’S Sdg-14 & Sdg-3 Using Python, N. Krishnapraveen, T. Muthuraji

Applications and Applied Mathematics: An International Journal (AAM)

Decision-making in sustainability oriented environments frequently involves bipolar evaluations, indeterminate information and phase dependent uncertainty that cannot be adequately represented by existing neutrosophic matrix models. To address this limitation, this study introduces a Bipolar Complex Neutrosophic Matrix (BCNM) framework that integrates bipolar semantics with complex valued uncertainty in a coherent algebraic structure. Fundamental operations and structural properties are rigorously established to ensure mathematical consistency. To facilitate practical multi criteria decision analysis (MCDA), novel score, accuracy, and hybrid aggregation operators are developed. The computational feasibility of the proposed approach is analyzed, demonstrating linear complexity with respect to the number of alternatives …

Qualitative Analysis Of Solutions To A General Class Of Nonlinear Difference Equations With Applications, Osama Moaaz, Mohamed F. Abouelenein, Mona Anis

Mathematical Modelling and Numerical Simulation with Applications

This work examines the qualitative behavior of a general class of difference equations. We establish criteria guaranteeing the stability, periodicity, and boundedness of the solutions of the equation under consideration. In addition, we identify its invariant intervals. The theoretical results are subsequently applied to various special cases, among them the May--Host model. Numerical simulations are presented to demonstrate the dynamics of the solutions and to validate the theoretical analysis.

Some Results In Maximal Pattern Complexity, Casey Schlortt

Electronic Theses and Dissertations

For a finite alphabet 𝒜 and a sequence 𝑥 ∈ 𝒜^ℕ_⊬ , Kamae and Zamboni combined the ideas of block complexity and topological sequence entropy to define the maximal pattern complexity, 𝑝^∗_𝑛 (𝑥). They defined an aperiodic sequence 𝑥 over two letters as pattern Sturmian if it had the lowest possible maximal pattern complexity, 2𝑛. Later, Kamae and Rao extended their definition of pattern Sturmian sequences to be sequences over ℓ ≥ 2 letters which are not periodic by projection and have maximal pattern complexity ℓ𝑛.

This dissertation answers a question posed by Kamae and Zamboni …

Obstructions To Some Injective Oriented Colourings, Russell J. Campbell, Nancy E. Clarke, Gary Macgillivray

Theory & Applications of Graphs

Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For each case in which such a problem is solvable in polynomial time, we identify a set $\mathcal{F}$ of oriented graphs such that an oriented graph $G$ has an injective oriented colouring with the given number of colours if and only if there is no $F \in \mathcal{F}$ for which there is a locally-injective homomorphism of $F$ to $G$.

The Connected Vertex Cover In Graphs, Kamran Mirasheh, Elham Mirashe, Ebrahim Vatandoost

Theory & Applications of Graphs

This paper presents tight bounds and characterizations for the vertex cover number and the connected vertex cover number of graphs. In particular, we identify all graphs for which βc(G) = |V (G)| − 1, proving that these are exactly the cycles and complete graphs. The analysis employs tools such as the degree matrix and the Rayleigh quotient to derive new and sharp upper bounds.

The $K$-Total Bondage Number Of A Graph, Jean-Pierre Appel, Gabrielle Fischberg, Kyle Kelley, Nathan B. Shank, Eliel Sosis

Theory & Applications of Graphs

Let \(G=(V,E)\) be a connected, finite undirected graph. A set \(S \subseteq V\) is said to be a total dominating set of \(G\) if every vertex in \(V\) is adjacent to some vertex in \(S\). The total domination number, \(\gamma_{t}(G)\), is the minimum cardinality of a total dominating set in \(G\). We define the \(k\)-total bondage of $G$ to be the minimum number of edges to remove from \(G\) so that the resulting graph has a total domination number at least \(k\) more than \(\gamma_{t}(G)\). In this work we establish general properties of \(k\)-total bondage and find exact values for …

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 …

Equitable Decompositions: A Gateway To Spectral Theory Through Graph Automorphisms, Daniel Ford

Master's Theses

Graphs with symmetry appear throughout mathematics and its applications, from the structure of molecules and network design to combinatorial game theory. A central question in spectral graph theory is how to compute or characterise the eigenvalues of the matrices associated with such graphs. Classical decomposition methods, such as diagonalisation or Jordan normal form, accomplish this but only once some spectral information is already known. A different approach, introduced by Barrett et al. (2015), uses the automorphisms of a graph to block-diagonalise its adjacency matrix without any prior spectral information. Because one of the resulting summands is always the quotient matrix …