Zero forcing, graphs on $k$ parallel paths, and linear preservers

Abstract

The zero forcing number of a simple loopless undirected graph, being an upper bound on the path cover number and the maximum nullity of the graph, is an important parameter in the study of the minimum rank problem. In this article, we show that the minimum $k$ for which a graph $G$ is a graph on $k$ parallel paths is an upper bound on the zero forcing number of $G$, and hence an upper bound on the path number and maximum nullity of $G$. We also determine an upper bound on the possible size (number of edges) of a graph on $k$ parallel paths. Finally we show that the only linear operators that preserve the zero forcing number of a graph are the vertex permutations.

Received: 24 October 2021 Accepted: 5 April 2022