The Zero Forcing Number of Graph Powers
Abstract
The $k$-th power of a simple graph $G$, denoted $G^k$, is the graph with vertex set $V(G)$ where two vertices are adjacent if they are within distance $k$ in $G$. We investigate the zero forcing number of graph powers. Powers of graphs are much denser and generally not encompassed by existing results on zero forcing of graphs, hence their study requires a different approach. In contrast with the usual zero forcing behavior under edge deletion, we show that the zero forcing parameter (and variations of it) is monotone with respect to taking powers. We also determine the zero forcing number of powers of paths and cycles, together with upper bounds for powers of spiders and of grids. We then present spectral lower bounds on the zero forcing number of graph powers which uniquely use the spectrum of the base graph, as well as linear programming methods to compute these bounds. Finally, we study the sharpness of the derived bounds. To derive our results we use techniques ranging from graph theory, linear algebra and polynomial optimization.