Digital Commons Network^™

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 …