.svg){kind=logo}
CONNECTED DOM-FORCING PROPAGATION TIMES IN GRAPHS
Keywords:
zero forcing number, dom-forcing number, connected propagation time, connected dom-forcing propagation timeDOI:
https://doi.org/10.17654/0974165826006Abstract
A zero forcing set $D_f \subseteq V(G)$ in a graph $G$ is called a dom-forcing set if $D_f$ is also a dominating set of $G$. The minimum cardinality of such a set is known as the dom-forcing number of the graph $G$, denoted by $F_d(G)$. If the subgraph induced by a dom-forcing set is connected, then it is called a connected dom-forcing set of the graph $G$. The minimum cardinality of such a set is called the connected domforcing number of $G$, denoted by $F_{c d}(G)$. The propagation time of a connected dom-forcing set of a graph $G$ is the minimum number of steps required to force all vertices to become black, starting from the vertices in the connected dom-forcing set and performing independent forces simultaneously. The connected dom-forcing propagation time of a graph is the minimum of propagation time taken over all minimum connected dom-forcing sets of the graph. We discuss the minimum connected dom-forcing propagation time of the graph $G$. Additionally, it delves into the precise determination of minimum connected dom-forcing propagation time for certain well-known graphs. Also, we characterize the class of graphs that admit connected dom-forcing propagation times $|V(G)|-1$ and $|V(G)|-2$.
Received: September 28, 2025
Revised: November 8, 2025
Accepted: November 14, 2025
References
[1] AIM Minimum Rank-special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428(7) (2008), 1628-1648.
[2] Allan Frendrup et al., An upper bound on the domination number of a graph with minimum degree 2, Discrete Math. 309(4) (2009), 639-646.
[3] Baby Chacko, Charles Dominic and K. P. Premodkumar, On the zero forcing number of graphs and their splitting graphs, Algebra Discrete Math. 28(1) (2019), 29-43.
[4] Samir K. Vaidya and Nirang J. Kothari, Domination integrity of splitting graph of path and cycle, International Scholarly Research Notices 2013(1) (2013), 795427.
[5] Hein van der Holst et al., Zero forcing parameters and minimum rank problems, Linear Algebra Appl. 433(2) (2010), 401-411.
[6] Leslie Hogben et al., Propagation time for zero forcing on a graph, Discrete Appl. Math. 160(13-14) (2012), 1994-2005.
[7] M. Khosravi, S. Rashidi and A. Sheikhhosseini, Connected zero forcing sets and connected propagation time of graphs, Transactions on Combinatorics 9(2) (2020), 77-88.
[8] P. Susanth, Charles Dominic and K. P. Premodkumar, Dom-forcing sets in graphs, 2024. arXiv preprint arXiv:2411.00580.
[9] P. Susanth, Charles Dominic and K. P. Premodkumar, Connected dom-forcing sets in graphs, Advances and Applications in Discrete Mathematics 42(7) (2025), 713-736.
[10] Nathan Warnberg, Positive semidefinite propagation time, Discrete Appl. Math. 198 (2016), 274-290.
[11] Tassos Dimitriou, Sotiris Nikoletseas and Paul Spirakis, The infection time of graphs, Discrete Appl. Math. 154(18) (2006), 2577-2589.
[12] S. Teresa Arockiamary, Total edge irregularity strength of diamond snake and dove, Int. J. Pure Appl. Math. 109 (2016), 125-132.
[13] J. Anitha, Zero forcing in snake graph, International Journal of Recent Technology and Engineering 7(5S2) (2019), 133-136.
[14] A. N. Hayyu et al., Resolving domination number of helm graph and it’s operation, Journal of Physics: Conference Series, IOP Publishing 1465(1) 2020, pp. 12-20.
[15] Dona John, Charles Dominic and Jobish Vallikavungal, Further results on the 3-consecutive vertex coloring number of certain graphs, IEEE Access 12 (2024), 144164-144173.
[16] I. Javaid et al., On the zero forcing number of corona and lexicographic product of graphs, 2016. arXiv preprint arXiv:1607.04071.
[17] Eric W. Weisstein, Connected domination number, MathWorld-A Wolfram Web Resource. https://mathworld.wolfram.com/ConnectedDominationNumber.html.
[18] S. N. Daoud and K. Mohamed, The complexity of some families of cycle-related graphs, Journal of Taibah University for Science 11(2) (2017), 205-228.
[19] E. Sampathkumar and H. B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979), 607-613.
[20] Daniela Ferrero et al., Note on power propagation time and lower bounds for the power domination number, J. Comb. Optim. 34(3) (2017), 736-741.
[21] Jesse Geneson and Leslie Hogben, Expected propagation time for probabilistic zero forcing, Australas. J. Combin. 83 (2022), 397-417.
[22] P. A. CrowdMath, Propagation time for weighted zero forcing, 2020. arXiv preprint arXiv:2005.07316.
[23] Joshua Carlson et al., Throttling positive semidefinite zero forcing propagation time on graphs, Discrete Appl. Math. 254 (2019), 33-46.
[24] Z. Rameh and E. Vatandoost, Some Cayley graphs with propagation time 1, Journal of the Iranian Mathematical Society 2(2) (2021), 111-122.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
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.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
