Zero-Forcing Processes on Proper Interval Graphs and Twisted Hypercubes

Abstract

Zero forcing is a graph infection process where a colour change rule is applied iteratively to a graph and an initial set of vertices, S. If S results in the entire graph becoming infected, we call this set a zero forcing set. The size of the smallest zero forcing set for a graph, G, is called the zero forcing number of G. We study subgraphs of proper interval graphs to determine how the removal of edges affects the zero forcing number of these graphs. We, then, compare the zero forcing number of twisted hypercubes to that of the same size hypercube, and determine that twisted hypercubes have smaller zero forcing number. Finally, we turn our attention to probabilistic zero forcing, a variant on zero forcing, and show that there are graphs who become forced faster when initiating the process from vertices that are outside the center of the graph.