Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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 …

An Alternate Proof For The Top-Heavy Conjecture On Partition Lattices Using Shellability, Brian Macdonald, Josh Hallam

Honors Thesis

A partially ordered set, or poset, is governed by an ordering that may or may not relate any pair of objects in the set. Both the bonds of a graph and the partitions of a set are partially ordered, and their poset structure can be depicted visually in a Hasse diagram. The partitions of {1, 2, ..., n} form a particularly important poset known as the partition lattice Πn. It is isomorphic to the bond lattice of the complete graph Kn, making it a special case of the family of bond lattices. Dowling and Wilson’s 1975 Top-Heavy Conjecture states that …

Domination In Graphs And The Removal Of A Matching, Geoffrey Boyer

All Theses

We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a nontrivial tree there is always a matching removal that increases the domination number; and if a graph has domination number at least $2$ there is always a maximal matching removal that does not double the domination number. We show that these results are sharp and discuss related questions.

Enumeration Of Increasing Trees, Garrett M. Southwood

Honors College Theses

We consider the generating function for increasingly labelled trees. By generalizing the proof through symbolic method, we are able to study various statistics regarding binary increasing trees with respect to height restrictions. We then apply our approach to special colorings of increasing trees in order to obtain their generating functions and, from there, derive the counting sequence for (ak+a)-colored recursive trees. We also present some interesting bijections between colored and non-colored increasing trees.

On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak

Theory & Applications of Graphs

The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …

Jumping Frogs On Cyclic Graphs, Jake Mitchell

Honors College Theses

From the traditional game of Solitaire to modern video games like Candy Crush and Five Nights at Freddy’s, single-player games have captivated audiences for gener- ations. We investigate a lesser-known single-player game, the Jumping Frogs problem, on various classes of simple graphs, a graph with no multiple edges or looped ver- tices. We determine whether frogs can be stacked together on one vertex of a given graph. In a graph with k vertices and one frog on each vertex, the frogs must make legal jumps to form a stack of k frogs. The problem is known to be solvable on …

Dna Self-Assembly Of Trapezohedral Graphs, Hytham Abdelkarim

Electronic Theses, Projects, and Dissertations

Self-assembly is the process of a collection of components combining to form an organized structure without external direction. DNA self-assembly uses multi-armed DNA molecules as the component building blocks. It is desirable to minimize the material used and to minimize genetic waste in the assembly process. We will be using graph theory as a tool to find optimal solutions to problems in DNA self-assembly. The goal of this research is to develop a method or algorithm that will produce optimal tile sets which will self-assemble into a target DNA complex. We will minimize the number of tile and bond-edge types …

A Pebbling Game On Powers Of Paths, Garth Isaak, Matthew Prudente, Joseph M. Marcinik Iii

Communications on Number Theory and Combinatorial Theory

Two Player Graph Pebbling is an extension of graph pebbling. Players Mover and Defender use pebbling moves, the act of removing two pebbles from one vertex and placing one pebble on an adjacent vertex, to win. If a specified vertex has a pebble on it, then Mover wins. If a specified vertex is pebble-free and there are no more valid pebbling moves, then Defender wins. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement of m pebbles and for any specified vertex, Mover can win. We specify the …

Bootstrap Percolation On Random Geometric Graphs, Alyssa Whittemore

Department of Mathematics: Dissertations, Theses, and Student Research

Bootstrap Percolation is a discrete-time process that models the spread of information or disease across the vertex set of a graph. We consider the following version of this process:

Initially, each vertex of the graph is set active with probability p or inactive otherwise. Then, at each time step, every inactive vertex with at least k active neighbors becomes active. Active vertices will always remain active. The process ends when it reaches a stationary state. If all the vertices eventually become active, then we say we achieve percolation.

This process has been widely studied on many families of graphs, deterministic …

Arithmetical Structures On Paths With A Doubled Edge, Darren B. Glass, Joshua R. Wagner

Math Faculty Publications

An arithmetical structure on a graph is given by a labeling of the vertices that satisfies certain divisibility properties. In this note, we look at several families of graphs and attempt to give counts on the number of arithmetical structures for graphs in these families.

Dna Complexes Of One Bond-Edge Type, Andrew Tyler Lavengood-Ryan

Electronic Theses, Projects, and Dissertations

DNA self-assembly is an important tool used in the building of nanostructures and targeted virotherapies. We use tools from graph theory and number theory to encode the biological process of DNA self-assembly. The principal component of this process is to examine collections of branched junction molecules, called pots, and study the types of structures that such pots can realize. In this thesis, we restrict our attention to pots which contain identical cohesive-ends, or a single bond-edge type, and we demonstrate the types and sizes of structures that can be built based on a single characteristic of the pot that is …

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …

A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler

Senior Independent Study Theses

Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.

Inverse Problems Related To The Wiener And Steiner-Wiener Indices, Matthew Gentry

College of Graduate Studies: Theses & Dissertations

In a graph, the generalized distance between multiple vertices is the minimum number of edges in a connected subgraph that contains these vertices. When we consider such distances between all subsets of $k$ vertices and take the sum, it is called the Steiner $k$-Wiener index and has important applications in Chemical Graph Theory. In this thesis we consider the inverse problems related to the Steiner Wiener index, i.e. for what positive integers is there a graph with Steiner Wiener index of that value?

Vertex-Relaxed Graceful Labelings Of Graphs And Congruences, Florin Aftene

Masters Theses & Specialist Projects

A labeling of a graph is an assignment of a natural number to each vertex

of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result …

Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green

Electronic Theses and Dissertations

To determine the function of a protein, we must know its 3-dimensional structure, which can be difficult to ascertain. Currently, predictive models are used to determine the structure of a protein from its sequence, but these models do not always predict the correct structure. To this end we use a nested graph model along with weighted invariants to minimize the errors and improve the accuracy of a predictive model to determine if we have the correct structure for a protein.

Gallai-Ramsey Numbers For C7 With Multiple Colors, Dylan Bruce

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H₁, ..., H_k, we write G → (H₁, ..., H_k), or G → (H)_k when H₁ = ··· = H_k = H, if every k-edge-coloring of G contains a monochromatic H_i in color i for some i ∈ …

Chromatic Polynomials And Orbital Chromatic Polynomials And Their Roots, Jazmin Ortiz

HMC Senior Theses

The chromatic polynomial of a graph, is a polynomial that when evaluated at a positive integer k, is the number of proper k colorings of the graph. We can then find the orbital chromatic polynomial of a graph and a group of automorphisms of the graph, which is a polynomial whose value at a positive integer k is the number of orbits of k-colorings of a graph when acted upon by the group. By considering the roots of the orbital chromatic and chromatic polynomials, the similarities and differences of these polynomials is studied. Specifically we work toward proving a conjecture …

Global Domination Stable Graphs, Elizabeth Marie Harris

Electronic Theses and Dissertations

A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.

Extremal Trees And Reconstruction, Andrew Ray

Department of Mathematics: Dissertations, Theses, and Student Research

Problems in two areas of graph theory will be considered.

First, I will consider extremal problems for trees. In these questions we examine the trees that maximize or minimize various invariants. For instance the number of independent sets, the number of matchings, the number of subtrees, the sum of pairwise distances, the spectral radius, and the number of homomorphisms to a fixed graph. I have two general approaches to these problems. To find the extremal trees in the collection of trees on n vertices with a fixed degree bound I use the certificate method. The certificate is a branch invariant, …

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller

Mathematical Sciences Technical Reports (MSTR)

We define G(n, k) to be a directed graph whose set of vertices is {0, 1, ..., n−1} and whose set of edges is defined by a modular relation. We say that G(n, k) is symmetric of order m if we can partition G(n, k) into subgraphs, each containing m components, such that all the components in a subgraph are isomorphic. We develop necessary and sufficient conditions for G(n, k) to contain symmetry when n is odd and square-free. Additionally, we use group theory to describe the structural properties of the subgraph of G(n, k) containing only those vertices relatively …

On The Attainability Of Upper Bounds For The Circular Chromatic Number Of K4-Minor-Free Graphs., Tracy Lance Holt

Electronic Theses and Dissertations

Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χ_c(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and …