Dissertation Defense Announcement

College of Arts and Sciences announces the Final Dissertation Defense of

Rebekah Herrman

for the Degree of Doctor of Philosophy
March 18, 2020 at 02:30 PM,Dunn Hall

Advisor: Bela Bollobas

Walks and games on graphs

ABSTRACT: In this dissertation, we look at five loosely connected topics. Continuous- time quantum walks have been well studied on graphs that do not change in time. We offer a mathematical formulation for expressing continuous- time quantum walks on graphs that can change in time, find a universal set of walks that can perform any operation, and use them to simulate basic quantum circuits. This work is joint with Travis Humble.

The (t,r) broadcast domination number of a graph G, $\gamma_{t,r}(G)$, is a generalization of the domination number of a graph. In Chapter 2, which is joint with Peter van Hitum, we consider the (t,r) broadcast domination number on graphs, specifically powers of cycles, powers of paths, and infinite grids.

Bridge-burning cops and robbers is a variant of the cops and robbers game on graphs in which the robber removes an edge from the graph once it is traversed. In Chapter 3, we study the maximum time it takes the cops to capture the robber in this variant. This is joint with Peter van Hintum and Stephen Smith.

In Chapter 4, joint with Andrew Carlotti, we study a variant of the chip-firing game called the diffusion game. In the diffusion game, there is some integer labelling of the vertices of a graph, and for each subsequent step every vertex simultaneously fires a chip to each neighbor with fewer chips. Long and Narayanan asked whether there exists an f(n) for each n, such that whenever we have a graph on n vertices and an initial allocation with at least f(n) chips on each vertex, then the number of chips on each vertex will remain non-negative. We show that f(n)=n-2 is the best possible bound.

In Chapter 5, we consider the eternal game chromatic number of random graphs. The eternal graph coloring is a version of the graph coloring game. In this chapter, we show that with high probability \chi_{g}^{\infty}(G_{n,p}) = (\frac{p}{2} + o(1))n for odd n, and also for even n when p=\frac{1}{k} for some k in N. This work is joint with Vojtěch Dvořák and Peter van Hintum.