Digital Commons Network^™

The Mathematical And Historical Significance Of The Four Color Theorem, Brock Bivens

Honors Theses

Researching how the Four Color Theorem was proved, its implications on the mathematical community, and interviews with working mathematicians to develop my own personal opinions on the significance of the Four Color Theorem.

Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham

All Theses

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Exploring The Structure Of Partial Difference Sets With Denniston Parameters, Nicolas Ferree

Honors Theses

In this work, we investigate the structure of particular partial difference sets (PDS) of size 70 with Denniston parameters in an elementary abelian group and in a nonelementary abelian group. We will make extensive use of character theory in our investigation and ultimately seek to understand the nature of difference sets with these parameters. To begin, we will cover some basic definitions and examples of difference sets and partial difference sets. We will then move on to some basic theorems about partial difference sets before introducing a group ring formalism and using it to explore several important constructions of partial …

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.

Zonality In Graphs, Andrew Bowling

Dissertations

Graph labeling and coloring are among the most popular areas of graph theory due to both the mathematical beauty of these subjects as well as their fascinating applications. While the topic of labeling vertices and edges of graphs has existed for over a century, it was not until 1966 when Alexander Rosa introduced a labeling, later called a graceful labeling, that brought the area of graph labeling to the forefront in graph theory. The subject of graph colorings, on the other hand, goes back to 1852 when the young British mathematician Francis Guthrie observed that the countries in a map …

Irregular Domination In Graphs, Caryn Mays

Dissertations

Domination in graphs has been a popular area of study due in large degree to its applications to modern society as well as the mathematical beauty of the topic. While this area evidently began with the work of Claude Berge in 1958 and Oystein Ore in 1962, domination did not become an active area of research until 1977 with the appearance of a survey paper by Ernest Cockayne and Stephen Hedetniemi. Since then, a large number of variations of domination have surfaced and provided numerous applications to different areas of science and real-life problems. Among these variations are domination parameters …

On 2-Primitive Triangle Decompositions Of Cocktail Party Graphs, Ian P. Waddell

Theses, Dissertations and Capstones

A decomposition of a graph Γ is a collection C of subgraphs, perhaps nonisomorphic, that partition the edges of Γ. Analogously, consider a group of truck drivers whose non-overlapping routes jointly cover all of the roads between a set of cities; that is, each road is traversed by precisely one driver. In this scenario, the cities are the vertices of the graph, the roads are the edges between vertices, and the drivers’ routes are the subgraphs in the decomposition. Given a graph H, we call C an H-decomposition of Γ if each subgraph in C is isomorphic to …

Investigations In The Semi-Strong Product Of Graphs And Bootstrap Percolation, Kevin J. Mccall

Theses and Dissertations

The semi-strong product of graphs G and H is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) x V(H). The edges of the semi-strong product are determined as follows: (g₁,h₁)(g₂,h₂) is an edge of the product whenever g₁g₂ is an edge of G and h₁h₂ is an edge of H or g₁ = g₂ and h₁h_{2 …}

Methods Of Computing Graph Gonalities, Noah Speeter

Theses and Dissertations--Mathematics

Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is …

Counting Spanning Trees On Triangular Lattices, Angie Wang

CMC Senior Theses

This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …

Graphs, Adjacency Matrices, And Corresponding Functions, Yang Hong

Honors Theses

Stable polynomials, in the context of this research, are two-variable polynomials like $p(z_1,z_2) = 2 - z_1 - z_2$ that are guaranteed to be non-zero if both input variables have an absolute value less than one in the complex plane. Stable polynomials are used in a variety of mathematical fields, thus finding ways to construct stable polynomials is valuable. An important property of these polynomials is whether they have boundary zeros, which are points in the complex plane where the polynomial equals zero and both variables have an absolute value of 1. Overall, it is challenging to find stable polynomials …

Rainbow Turan Methods For Trees, Victoria Bednar

Theses and Dissertations

The rainbow Turan number, a natural extension of the well-studied traditional
Turan number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstraete. The rainbow Tur ́an number of a graph F , ex*(n, F ), is the largest number of edges for an n vertex graph G that can be properly edge colored with no rainbow F subgraph. Chapter 1 of this dissertation gives relevant definitions and a brief history of extremal graph theory. Chapter 2 defines k-unique colorings and the related k-unique Turan number and provides preliminary results on this new variant. In Chapter 3, we explore the …

Selected Problems In Graph Coloring, Hudson Lafayette

Theses and Dissertations

The Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4.

For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.

3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel Mccann

Mathematical Sciences Undergraduate Honors Theses

The complete 3-uniform hypergraph of order v is denoted as K_v and consists of vertex set V with size v and edge set E, containing all 3-element subsets of V. We consider a 3-uniform hypergraph P₇, a path with vertex set {v₁, v₂, v₃, v₄, v₅, v₆, v₇} and edge set {{v₁, v₂, v₃}, {v₂, v₃, v₄}, {v₄, v₅, v₆}, {v₅, v_{6 …}

Minimality Of Integer Bar Visibility Graphs, Emily Dehoff

University Honors Theses

A visibility representation is an association between the set of vertices in a graph and a set of objects in the plane such that two objects have an unobstructed, positive-width line of sight between them if and only if their two associated vertices are adjacent. In this paper, we focus on integer bar visibility graphs (IBVGs), which use horizontal line segments with integer endpoints to represent the vertices of a given graph. We present results on the exact widths of IBVGs of paths, cycles, and stars, and lower bounds on trees and general graphs. In our main results, we find …

Local-Global Results On Discrete Structures, Alexander Lewis Stevens

Electronic Theses and Dissertations

Local-global arguments, or those which glean global insights from local information, are central ideas in many areas of mathematics and computer science. For instance, in computer science a greedy algorithm makes locally optimal choices that are guaranteed to be consistent with a globally optimal solution. On the mathematical end, global information on Riemannian manifolds is often implied by (local) curvature lower bounds. Discrete notions of graph curvature have recently emerged, allowing ideas pioneered in Riemannian geometry to be extended to the discrete setting. Bakry- Émery curvature has been one such successful notion of curvature. In this thesis we use combinatorial …

Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer

Theses and Dissertations--Computer Science

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …

On The Hamiltonicity Of Subgroup Lattices, Nicholas Charles Fleece

MSU Graduate Theses

In this paper we discuss the Hamiltonicity of the subgroup lattices of

different classes of groups. We provide sufficient conditions for the

Hamiltonicity of the subgroup lattices of cube-free abelian groups. We also

prove the non-Hamiltonicity of the subgroup lattices of dihedral and

dicyclic groups. We disprove a conjecture on non-abelian p-groups by

producing an infinite family of non-abelian p-groups with Hamiltonian

subgroup lattices. Finally, we provide a list of the Hamiltonicity of the

subgroup lattices of every finite group up to order 35 barring two groups.

On Problems In Random Structures, Ryan Cushman

Dissertations

This work addresses two problems in optimizing substructures within larger random structures. In the first, we study the triangle-packing number v(G), which is the maximum size of a set of edge-disjoint triangles in a graph. In particular we study this parameter for the random graph G(n,m). We analyze a random process called the online triangle packing process in order to bound v(G). The lower bound on v(G(n,m)) that this produces allows for the verification of a conjecture of Tuza for G( …

Trees With Unique Italian Dominating Functions Of Minimum Weight, Alyssa England

Electronic Theses and Dissertations

An Italian dominating function, abbreviated IDF, of $G$ is a function $f \colon V(G) \rightarrow \{0, 1, 2\}$ satisfying the condition that for every vertex $v \in V(G)$ with $f(v)=0$, we have $\sum_{u \in N(v)} f(u) \ge 2$. That is, either $v$ is adjacent to at least one vertex $u$ with $f(u) = 2$, or to at least two vertices $x$ and $y$ with $f(x) = f(y) = 1$. The Italian domination number, denoted $\gamma_I$(G), is the minimum weight of an IDF in $G$. In this thesis, we use operations that join two trees with a single edge in order …

Extremal Problems On Induced Graph Colorings, James Hallas

Dissertations

Graph coloring is one of the most popular areas of graph theory, no doubt due to its many fascinating problems and applications to modern society, as well as the sheer mathematical beauty of the subject. As far back as 1880, in an attempt to solve the famous Four Color Problem, there have been numerous examples of certain types of graph colorings that have generated other graph colorings of interest. These types of colorings only gained momentum a century later, however, when in the 1980s, edge colorings were studied that led to vertex colorings of various types, led by the introduction …

Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature Of Graphs, And Linear Algebra, Zhiyu Wang

Theses and Dissertations

This thesis studies some problems in extremal and probabilistic combinatorics, Ricci curvature of graphs, spectral hypergraph theory and the interplay between these areas. The first main focus of this thesis is to investigate several Ramsey-type problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and spectral techniques:

• The size-Ramsey number Rˆ(G, r) is defined as the minimum number of edges in a hypergraph H such that every r-edge-coloring of H contains a monochromatic copy of G in H. We improved a result of Dudek, La Fleur, Mubayi and Rödl [ J. Graph Theory 2017 ] on the size-Ramsey number …

Complete Bipartite Graph Embeddings On Orientable Surfaces Using Cayley Maps, Madeline Spies

Honors Program Theses

We explored how effective Cayley Maps are at embedding complete bipartite graphs onto orientable surfaces, such as spheres and tori. We embedded the graphs onto surfaces using Cayley Maps with the intent of finding rotations that result in the graphs’ optimal genera. Because there are only three groups that can be used to describe Kp,p, where p is prime, we chose to focus on this specific graph type. This paper explains how we determined the genera when using a Cayley Map, provides general theorems for surface face sizes and the Dihedral Group, and discusses our results for Kp,p up to …

Roman Domination Cover Rubbling, Nicholas Carney

Electronic Theses and Dissertations

In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the …

Variations In Ramsey Theory, Drake Olejniczak

Dissertations

The Ramsey number R(F,H) of two graphs F and H is the smallest positive integer n for which every red-blue coloring of the (edges of a) complete graph of order n results in a graph isomorphic to F all of whose edges are colored red (a red F) or a blue H. Beineke and Schwenk extended this concept to a bipartite version of Ramsey numbers, namely the bipartite Ramsey number BR(F,H) of two bipartite graphs F and H is the smallest positive integer rsuch that every red-blue coloring of the r-regular complete bipartite graph results in either …

Counting And Coloring Sudoku Graphs, Kyle Oddson

Mathematics and Statistics Dissertations, Theses, and Final Project Papers

A sudoku puzzle is most commonly a 9 × 9 grid of 3 × 3 boxes wherein the puzzle player writes the numbers 1 - 9 with no repetition in any row, column, or box. We generalize the notion of the n² × n² sudoku grid for all n ϵ Z ^≥2 and codify the empty sudoku board as a graph. In the main section of this paper we prove that sudoku boards and sudoku graphs exist for all such n we prove the equivalence of [3]'s construction using unions and products of graphs to the definition of …

Kings In The Direct Product Of Digraphs, Morgan Norge

Theses and Dissertations

A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

Electronic Theses and Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound …

Italian Domination On Ladders And Related Products, Bradley Gardner

Electronic Theses and Dissertations

An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination …