The $q$-Analogue of Zero Forcing for Certain Families of Graphs

Abstract

Zero forcing is a combinatorial game played on a graph with the ultimate goal of changing the colour of all the vertices at minimal cost. Originally this game was conceived as a one player game, but later a two-player version was devised in-conjunction with studies on the inertia of a graph, and has become known as the $q$-analogue of zero forcing. In this paper, we study and compute the $q$-analogue zero forcing number for various families of graphs. We begin with by considering a concept of contraction associated with trees. We then significantly generalize an equation between this $q$-analogue of zero forcing and a corresponding nullity parameter for all threshold graphs. We close by studying the $q$-analogue of zero forcing for certain Kneser graphs, and a variety of cartesian products of structured graphs.

29 pages