The zero forcing number of expanded paths and cycles

Abstract

The zero forcing number is defined as the minimum size of a zero forcing set, and features as an upper bound for the graph nullity. An expanded path $Pm_1,m_2,...,m_k$ (resp. expanded cycle $Cm_1,m_2,...,m_k$ ) is obtained from the $k$-vertex path (cycle) by replacing the $i$th vertex with an independent set of $m_i$ vertices. We prove that the zero forcing number of $Pm_1,m_2,...,m_k$ (resp. $Cm_1,m_2,...,m_k$ ) belongs to ${n−k, n−k+1} ({n−k+1, n−k+2})$, where $n$ is the number of vertices. It is also decided for which expanded paths and expanded cycles the zero forcing number is $n − k + 1$. As an application, we offer a new proof of the result of Liang, Li and Xu that gives a characterization of triangle-free graphs with zero forcing number $n − 3$. We also show that the zero forcing number of a cycle-spliced graph (i.e., a connected graph whose every block is a cycle) is $c + 1$, where $c$ is the cyclomatic number. This result induces an upper bound for the nullity of a cycle-spliced graph and extends the result of Wong, Zhou and Tian concerning the bipartite case.