Discrete Mathematics and Combinatorics Commons^™

Discrete Math For Computer Science - Chapter 6: Proofs By Contradiction: Proofs By Cases, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 5: Direct Proofs: Proofs By Contrapositive, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 7: Sets And Subsets: Set Of Sets, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

On Realizability Of Some Graphs, Runze Wang

Communications on Number Theory and Combinatorial Theory

A graph H is said to be realizable by a graph G if for any vertex v in G, the induced subgraph of G on the neighborhood of v is isomorphic to H. In this paper, we show that a complete multipartite graph is realizable if and only if each of its parts has the same size; characterize the graphs by which a complete multipartite graph with each part having the same size is realizable; show that all cluster graphs are realizable; prove that a wheel is realizable if and only if it has four vertices; prove that …

Two Families Of Graceful Cacti, Christian Barrientos

Communications on Number Theory and Combinatorial Theory

We present a graceful labeling for each member of a subfamily of quadrangular cacti whose underlying graph correspond to the subclass of rooted binary trees where every level has at most two vertices. We also prove the existence of an $\alpha$-labeling (the most restricted type of graceful labeling) for all cyclic snakes, i.e., those cacti whose blocks are copies of the cycle $C_{4n}$ and its maximum degree is four.

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

Theory & Applications of Graphs

For a plane graph $G = (V, E)$ embedded in $\mathbb{R}^2$, let $\mathcal{F}(G)$ denote the set of faces of $G$. Then, $G$ is called a \textit{$C_n$-face-magic graph} if there exists a bijection $f: V(G) \to \{1, 2, \dots, |V(G)|\}$ such that for any $F \in \mathcal{F}(G)$ with $F \cong C_n$, the sum of all the vertex labels along $C_n$ is a constant $c$. In this paper, we investigate face-magic labelings of polygonal graphs.

A Characterization Of Chordal Graph Without Sun And Co-Rising Sun As Convex Geometry, Silvia B. Tondato

Theory & Applications of Graphs

In this paper we introduce the notion of $t_3$ \textit{convexity}, a natural restriction of triangle convexity. A \textit{triangle path} is a path allowing just short chords. A triangle path $P$ between two non-adjacent vertices in a graph $G$ is called $t_3$ \textit{path} if the first vertex of $P$ is among vertices from $P$ adjacent only to the second vertex of $P$, and the last vertex of $P$ is among vertices from $P$ adjacent only to the second-last vertex of $P$. A set $S \subseteq V(G)$ is $t_3$ \textit{convex} if for any two non-adjacent vertices $x, y \in S$ any vertex …

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 …

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 …

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, …

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 …

Codes From Incidence Matrices Of Hypergraphs, Sudipta Mallik, Bahattin Yildiz

Mathematics Faculty Research

Binary codes are constructed from incidence matrices of hypergraphs. A combinatorial description is given for the minimum distances of such codes via a combinatorial tool called “eonv”. This combinatorial approach provides a faster alternative method of finding the minimum distance, which is known to be a hard problem. This is demonstrated on several classes of codes from hypergraphs. In particular the “eonv” method is used to prove that the minimum distance of codes from incidence matrices of complete 3-partite 3-uniform hypergraphs with partite set size of n is n2. A lower bound on the minimum distances of codes from …

Coloring Trivalent Graphs: A Defect Tft Approach, Amit Kumar

LSU Doctoral Dissertations

We show that the combinatorial matter of graph coloring is, in fact, quantum in the sense of satisfying the sum over all the possible intermediate state properties of a path integral. In our case, the topological field theory (TFT) with defects gives meaning to it. This TFT has the property that when evaluated on a planar trivalent graph, it provides the number of Tait-Coloring of it. Defects can be considered as a generalization of groups. With the Klein-four group as a 1-defect condition, we reinterpret graph coloring as sections of a certain bundle, distinguishing a coloring (global-sections) from a coloring …

Counting The Classes Of Projectively-Equivalent Pentagons On Finite Projective Planes Of Prime Order, Maxwell Hosler

Rose-Hulman Undergraduate Mathematics Journal

In this paper, we examine the number of equivalence classes of pentagons on finite projective planes of prime order under projective transformations. We are interested in those pentagons in general position, meaning that no three vertices are collinear. We consider those planes which can be constructed from finite fields of prime order, and use algebraic techniques to characterize them by their symmetries. We are able to construct a unique representative for each pentagon class with nontrivial symmetries. We can then leverage this fact to count classes of pentagons in general. We discover that there are (1/10)((p+3)(p-3)+4 …