Failed zero forcing numbers of grassmann graphs

Afzali, Fatemeh; Ghodrati, Amir Hossein; Maimani, Hamid Reza

doi:10.22108/toc.2025.145774.2295

تعداد نشریات	44
تعداد شماره‌ها	1,877
تعداد مقالات	15,278
تعداد مشاهده مقاله	43,730,711
تعداد دریافت فایل اصل مقاله	17,563,018

	Failed zero forcing numbers of grassmann graphs
Transactions on Combinatorics
دوره 15، شماره 4، اسفند 2026، صفحه 295-304 اصل مقاله (510.14 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2025.145774.2295
نویسندگان
Fatemeh Afzali¹؛ Amir Hossein Ghodrati^* ¹؛ Hamid Reza Maimani²
¹Department of Mathematics, Faculty of Science Shahid Rajaee, Teacher Training University, Tehran, Iran
²Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran.
چکیده
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)$.
کلیدواژه‌ها
Failed zero forcing number؛ Grassmann graph؛ Projective plane؛ Affine plane

مراجع
[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.
آمار تعداد مشاهده مقاله: 304 تعداد دریافت فایل اصل مقاله: 378

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Failed zero forcing numbers of grassmann graphs