Discrete Mathematics and Combinatorics Commons^™

Discrete Math For Computer Science - Chapter 10: Definition Of Functions: Properties Of Functions, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

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