Degree Type

Dissertation

Date of Award

2019

Degree Name

Doctor of Philosophy

Department

Mathematics

Major

Mathematics

First Advisor

Leslie Hogben

Abstract

Zero forcing is a combinatorial game played on graphs in which a color change rule is used to progressively change the color of vertices from white to blue. The (standard) color change rule is that a blue vertex u can force a white vertex w to become blue if w is the only white vertex adjacent to u. When using the color change rule, the goal is to eventually change the color of every vertex in the graph to blue. Some interesting questions arise from this process that are heavily studied. What is the smallest possible size of an initial set of blue vertices that can eventually color the entire graph blue? How much time is required to complete this process? The answer to the first question is called the zero forcing number of a graph and the answer to the second question is called the propagation time of the initial set. A more recent area of study is throttling which balances the cost of the initial set with the cost of its propagation time in order to make the process as efficient as possible. Specifically, the (standard) throttling number of a graph is the minimum value of the sum of the size of an initial set and its propagation time taken over all possible initial sets. Many variations of the color change rule also lead to variations of propagation time and throttling. These include positive semidefinite (PSD) zero forcing, the minor monotone floor of zero forcing, and the minor monotone floor of PSD zero forcing. In this dissertation, general definitions are given that allow for the study of propagation and throttling for many variants of zero forcing. In addition, a technique is introduced that is used to characterize all graphs with specified throttling numbers. This technique is then generalized and applied to obtain similar characterizations for the variants of zero forcing mentioned above.

Copyright Owner

Joshua Carlson

Language

en

File Format

application/pdf

File Size

74 pages

Included in

Mathematics Commons

Share

COinS