Revista de la
Unión Matemática Argentina
The zero forcing number of expanded paths and cycles
Yipeng Liao, Chaohui Chen, Jia Wei, and Zoran Stanić

Volume 69, no. 1 (2026), pp. 45–53    

Published online (final version): November 19, 2025

https://doi.org/10.33044/revuma.5022

Download PDF

Abstract

The zero forcing number, defined as the minimum size of a zero forcing set, serves as an upper bound for the graph nullity. An expanded path $P_{m_1, m_2, \ldots, m_k}$ (resp. expanded cycle $C_{m_1, m_2, \ldots, m_k}$) is obtained from the $k$-vertex path (resp. cycle) by replacing its $i$th vertex with an independent set of $m_i$ vertices. We show that the zero forcing number of $P_{m_1, m_2, \ldots, m_k}$ (resp. $C_{m_1, m_2, \ldots, m_k}$) belongs to $\{n-k, n-k+1\}$ (resp. $\{n-k+1, n-k+2\}$), where $n$ is the number of vertices, and determine when it equals $n-k+1$. As an application, we provide a new proof of a result of Liang, Li, and Xu characterizing triangle-free graphs with zero forcing number $n-3$. We also show that for any cycle-spliced graph (i.e., a connected graph all of whose blocks are cycles), the zero forcing number equals $c+1$, where $c$ is the cyclomatic number. This gives an upper bound for the nullity and extends a result of Wong, Zhou, and Tian for the bipartite case.

References

  1. AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 no. 7 (2008), 1628–1648.  DOI  MR  Zbl
  2. J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, 2008.  MR  Zbl
  3. A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012.  DOI  MR  Zbl
  4. D. Burgarth, S. Bose, C. Bruder, and V. Giovannetti, Local controllability of quantum networks, Phys. Rev. A 79 no. 6 (2009), Paper No. 060305.  DOI
  5. D. Burgarth, D. D'Alessandro, L. Hogben, S. Severini, and M. Young, Zero forcing, linear and quantum controllability for systems evolving on networks, IEEE Trans. Automat. Control 58 no. 9 (2013), 2349–2354.  DOI  MR  Zbl
  6. D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 no. 10 (2007), Paper No. 100501.  DOI
  7. B. Cheng and B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007), 60–67.  DOI  MR  Zbl
  8. R. Davila and F. Kenter, Bounds for the zero forcing number of graphs with large girth, Theory Appl. Graphs 2 no. 2 (2015), Article 1.  DOI  MR  Zbl
  9. S. English, C. MacRury, and P. Prałat, Probabilistic zero forcing on random graphs, European J. Combin. 91 (2021), Paper No. 103207.  DOI  MR  Zbl
  10. Y.-Z. Fan and K.-S. Qian, On the nullity of bipartite graphs, Linear Algebra Appl. 430 no. 11-12 (2009), 2943–2949.  DOI  MR  Zbl
  11. M. Gentner, L. D. Penso, D. Rautenbach, and U. S. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016), 196–200.  DOI  MR  Zbl
  12. T. Kalinowski, N. Kamčev, and B. Sudakov, The zero forcing number of graphs, SIAM J. Discrete Math. 33 no. 1 (2019), 95–115.  DOI  MR  Zbl
  13. Y.-P. Liang, J. Li, and S.-J. Xu, On extremal graphs for zero forcing number, Graphs Combin. 38 no. 6 (2022), Paper No. 185.  DOI  MR  Zbl
  14. D. D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl. 436 no. 12 (2012), 4423–4432.  DOI  MR  Zbl
  15. D. Wong, Q. Zhou, and F. Tian, Nullity and singularity of a graph in which every block is a cycle, Discrete Math. 345 no. 6 (2022), Paper No. 112851.  DOI  MR  Zbl
  16. M. Zhao, L. Kang, and G. J. Chang, Power domination in graphs, Discrete Math. 306 no. 15 (2006), 1812–1816.  DOI  MR  Zbl