Failed zero forcing numbers of grassmann graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Faculty of Science Shahid Rajaee, Teacher Training University, Tehran, Iran

2 Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran.

Abstract

For a graph $G$ with vertices colored either black or white, consider the following rule to change the colors: the color of a vertex which is the only white neighbor of a black vertex, changes from white to black. A proper subset $S$ of the vertex set of $G$ is called a failed zero forcing set if, regardless of how many times this rule is applied to a graph with the initial black vertices $S$, at least one white vertex always remains. The maximum size of such a subset is called the failed zero forcing number of $G$ and is denoted by $F(G)$. In this paper, we look at the failed zero forcing numbers of Grassmann graphs $J_q(n, 2)$ and prove that $F(J_q(n, 2))={n \brack 2}_q - b'_2(q)$, for $n\geq 5$, where $b'_2(q)$ is the maximum number of points in the affine or projective plane of order $q$ such that there is no line that passes through exactly one of these points. Moreover, using maximum arcs in the projective planes, we show that if $q$ is a power of two, then $F(J_q(n, 2))={n \brack 2}_q - (q + 2)$.

Keywords

Main Subjects

References

[1] F. Barioli, W. Barrett, S. Butler, S. M. Cioaba, D. Cvetkovic, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovic, H. van der Holst, K. V. Meulen and A. W. Wehe, AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428 (2008) 1628–1648.
[2] F. Afzali, A. H. Ghodrati, H. R. Maimani, Failed zero forcing numbers of Kneser graphs, Johnson graphs and hypercubes, J. Appl. Math. comput., 70 no. 3 (2024) 2665–2675.
[3] F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Zero forcing parameters and minimum rank problems, Linear Algebra Appl., 433 (2010) 401–411.
[4] S. Bolusani, M. Besan¸con, K. Bestuzheva, A. Chmiela, Jo. Dion´ısio, T. Donkiewicz, J. van Doornmalen, L. Eifler, M. Ghannam, A. Gleixner, C. Graczyk, K. Halbig, I. Hedtke, A. Hoen, C. Hojny, R. van der Hulst, D. Kamp, T. Koch, K. Kofler, J. Lentz, J. Manns and G. Mexi, E. M¨uhmer, M. E. Pfetsch, F. Schl¨osser, F. Serrano, Y. Shinano, M. Turner, S. Vigerske, D. Weninger and L. Xu, The SCIP optimization suite 9.0, The release report of the SCIP Optimization Suite version 9.0, (2024). https://doi.org/10.48550/arXiv.2402.17702
[5] S. M. Fallat and L. Hogben, Minimum rank, maximum nullity, and zero forcing number of graphs, in: L. Hogben (ed.), Chapter 46 of Handbook of Linear Algebra, second edition, CRC Press, Boca Raton, FL, 2014, 1–46.
[6] S. M. Fallat and L. Hogben, The minimum rank of symmetric matrices described by a graph: A survey, Linear Algebra Appl., 426 no. 2-3 (2007) 558–582.
[7] K. Fetcie, B. Jacob and D. Saavedra, The failed zero forcing number of a graph, Involve, 8 no. 1 (2015) 99–117.
[8] L. Gomez, K. Rubi, J. Terrazas and D. A. Narayan, All graphs with a failed zero forcing number of two, Symmetry, 13 no. 11, 2221 (2021).
[9] J. P. W. Hirschfeld, Projective geometries over finite fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979.
[10] S. Jukna, Extremal combinatorics. With applications in computer science, Second Edition, Springer, Heidelberg, 2011.
[11] SageMath, The sage mathematics software system (Version 10.2), The Sage Developers, 2023, https://www.sagemath.org.
[12] Y. Shitov, On the complexity of failed zero forcing, Theoret. Comput. Sci., 660 (2017) 102–104.
[13] N. Swanson and E. Ufferman, A lower bound on the failed zero forcing number of a graph, Involve, 16 no. 3 (2023) 493–504.
Transactions on Combinatorics
Volume 15, Issue 4 - Serial Number 4
December 2026
Pages 295-304

Files

History

  • Receive Date: 29 June 2025
  • Revise Date: 01 November 2025
  • Accept Date: 17 November 2025
  • Published Online: 20 November 2025

Share

How to cite

Statistics