.svg){kind=logo}
ON THE PROPAGATION NUMBER OF SOME GRAPHS
Keywords:
k-forcing set, zero-forcing number, propagation numberDOI:
https://doi.org/10.17654/0972087126027Abstract
Let $G=(V, E)$ be a graph and $k$ be a positive integer. A set $S \subseteq V$ is a $k$-forcing set if its vertices are initially colored, while the remaining vertices are initially non-colored, and the graph is subjected to the following color change rule such that all vertices in $G$ will eventually become colored. A colored vertex with at most $k$ noncolored neighbors will cause each non-colored neighbor to become colored. The $k$-forcing number, denoted by $F_k(G)$, is the cardinality of a smallest $k$-forcing set. Let $v \in V$. The propagation number of $G$ relative to $v$, denoted by $\rho_\nu(G)$, is the smallest $k$ such that $\{v\}$ is a $k$-forcing set of $G$. This study also gives the propagation number of paths, cycles, complete graphs, the join of some classes of graphs, the corona of some classes of graphs, the Cartesian product of some classes of graphs, wheel-related graphs, cycle-related graphs, and uniform $n$-star split graphs.
Received: September 28, 2025
Accepted: November 12, 2025
References
[1] D. Amos, Y. Caro, R. Davila and R. Pepper, Upper bounds on the k-forcing number of a graph, Discrete Applied Mathematics 181 (2015), 1-10.
[2] F. Barioli, S. M. Fallat and R. L. Smith, On acyclic and unicyclic graphs whose minimum rank equals the diameter, Linear Algebra and its Applications 429(7) (2008), 1568-1578.
[3] B. Brimkov and R. Davila, Characterizations of the connected forcing number of a graph, 2016. arXiv preprint arXiv:1604.00740.
[4] D. Burgarth, V. Giovannetti, L. Hogben, S. Severini and M. Young, Logic circuits from zero forcing, Natural Computing 14(3) (2015), 485-490.
[5] Y. Caro, R. Davila and R. Pepper, Extremal k-forcing sets in oriented graphs, Discrete Applied Mathematics 262 (2019), 42-55.
[6] Y. Caro and R. Pepper, Dynamic approach to k-forcing, 2014. arXiv preprint arXiv:1405.7573.
[7] R. Davila and M. A. Henning, On the total forcing number of a graph, Discrete Applied Mathematics 257 (2019), 115-127.
[8] R. Davila, M. A. Henning, C. Magnant and R. Pepper, Bounds on the connected forcing number of a graph, Graphs and Combinatorics 34(6) (2018), 1159-1174.
[9] R. Davila and F. Kenter, Bounds for the zero-forcing number of graphs with large girth, 2014. arXiv preprint arXiv:1406.0482.
[10] R. R. Davila, Bounding the forcing number of a graph, Ph. D. Thesis, 2015.
[11] D. Ferrero, L. Hogben, F. H. Kenter and M. Young, The relationship between k-forcing and k-power domination, Discrete Mathematics 341(6) (2018), 1789-1797.
[12] M. Gentner, L. D. Penso, D. Rautenbach and U. S. Souza, Extremal values and bounds for the zero forcing number, Discrete Applied Mathematics 214 (2016), 196-200.
[13] M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Applied Mathematics 236 (2018), 203-213.
[14] F. Harary, Graph theory, Reading, Massachusetts: Addison-Wesley Publishing Company, 1969.
[15] T. Kalinowski, N. Kamcev and B. Sudakov, The zero forcing number of graphs, SIAM Journal on Discrete Mathematics 33(1) (2019), 95-115.
[16] L. Lu, B. Wu and Z. Tang, Proof of a conjecture on the zero forcing number of a graph, Discrete Applied Mathematics 213 (2016), 233-237.
[17] S. A. Meyer, Zero forcing sets and bipartite circulants, Linear Algebra and its Applications 436 (2012), 888-900.
[18] Z. Montazeri and N. Soltankhah, k-forcing number for cartesian product of some graphs, Contributions to Discrete Mathematics 16(1) (2021), 89-97.
[19] K. Premodkmuar, C. Dominic and B. Chacko, Connected k-forcing sets of graphs and splitting graphs, J. Math. Comput. Sci. 10(3) (2020), 656-680.
[20] K. Premodkumar, C. Dominic and B. Chacko, Two distance forcing number of a graph, J. Math. Comput. Sci. 10(6) (2020), 2233-2248.
[21] M. Raksha and C. Dominic, On the k-forcing Number of some ds-graphs, Data Science and Security, Springer, 2021, 394-402.
[22] Y. Zhao, L. Chen and H. Li, On tight bounds for the k-forcing number of a graph, Bulletin of the Malaysian Mathematical Sciences Society 42(2) (2019), 743-749.
[23] V. L. Banot, G. A. J. Alcoran-Alvarez, J. G. Adanza and M. P. Baldado Jr., Forcing number of some wheel-related graphs, Science International (Lahore) 35(3) (2023), 249-255.
[24] V. L. Banot and M. P. Baldado Jr., k-Forcing number of some cycle-related graphs, Science International (Lahore) 35(4) (2023), 455-457.
[25] V. L. Banot, k-Forcing number of uniform n-star split graphs, Science International (Lahore) 35(4) (2023), 485-487.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Copyright ©2025 The Author(s)
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Non-Commercial Use: For non-commercial purposes only. No commercial activities without explicit permission.
Contact Puspha Publishing House for more info or permissions.
