Let $ G $ be a connected graph. We investigated structural relationships between the zero forcing number $ Z(G) $ and connected domination. Our main result proved that the complement of every minimal connected dominating set formed a zero forcing set, establishing the converse direction to a known result of Amos et al. and yielding the inequality $ Z(G)+\gamma_c(G)\le |V(G)| $. We further studied graphs attaining equality and showed that several natural graph families, including complete multipartite graphs, satisfied it. Motivated by the duality between forcing and domination, we introduced the dom-forcing number $ F_d(G) $, the minimum size of a set that was both dominating and zero forcing. We established sharp general bounds, determined its exact values for paths, stars, complete graphs, and complete bipartite graphs, and characterized when it equaled the zero forcing number or the domination number. Finally, we discussed several open problems related to forcing-domination dualities.
Citation: Haining Jiang, Haiyun Wan. Forcing and domination in graphs[J]. AIMS Mathematics, 2026, 11(7): 19772-19783. doi: 10.3934/math.2026802
Let $ G $ be a connected graph. We investigated structural relationships between the zero forcing number $ Z(G) $ and connected domination. Our main result proved that the complement of every minimal connected dominating set formed a zero forcing set, establishing the converse direction to a known result of Amos et al. and yielding the inequality $ Z(G)+\gamma_c(G)\le |V(G)| $. We further studied graphs attaining equality and showed that several natural graph families, including complete multipartite graphs, satisfied it. Motivated by the duality between forcing and domination, we introduced the dom-forcing number $ F_d(G) $, the minimum size of a set that was both dominating and zero forcing. We established sharp general bounds, determined its exact values for paths, stars, complete graphs, and complete bipartite graphs, and characterized when it equaled the zero forcing number or the domination number. Finally, we discussed several open problems related to forcing-domination dualities.
| [1] |
Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428 (2008), 1628–1648. https://doi.org/10.1016/j.laa.2007.10.009 doi: 10.1016/j.laa.2007.10.009
|
| [2] |
D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl., 436 (2012), 4423–4432. https://doi.org/10.1016/j.laa.2011.05.012 doi: 10.1016/j.laa.2011.05.012
|
| [3] |
R. Davila, T. Kalinowski, S. Stephen, A lower bound on the zero forcing number, Discr. Appl. Math., 250 (2018), 363–367. https://doi.org/10.1016/j.dam.2018.04.015 doi: 10.1016/j.dam.2018.04.015
|
| [4] |
N. Ison, M. Kempton, F. Kenter, Zero forcing on 2-connected outerplanar graphs, Graphs Combin., 42 (2026), 51. https://doi.org/10.1007/s00373-026-03045-5 doi: 10.1007/s00373-026-03045-5
|
| [5] |
F. Kheyridoost, E. Vatandoost, Zero forcing number and propagation time discrepancy of some graphs, Trans. Combin., 15 (2026), 215–230. https://doi.org/10.22108/toc.2025.142214.2195 doi: 10.22108/toc.2025.142214.2195
|
| [6] |
D. Amos, Y. Caro, R. Davila, R. Pepper, Upper bounds on the $ k $-forcing number of a graph, Discr. Appl. Math., 181 (2015), 1–10. https://doi.org/10.1016/j.dam.2014.08.029 doi: 10.1016/j.dam.2014.08.029
|
| [7] | E. Sampathkumar, H. B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci., 13 (1979), 607–613. |
| [8] |
L. Guo, W. Ning, Connectivity and super connectivity of enhanced folded hypercube-like networks, Discr. Appl. Math., 369 (2025), 14–19. https://doi.org/10.1016/j.dam.2025.02.034 doi: 10.1016/j.dam.2025.02.034
|
| [9] |
L. Guo, X. Kong, Component edge connectivity of folded hypercube-like networks, Discr. Appl. Math., 378 (2026), 162–170. https://doi.org/10.1016/j.dam.2025.07.011 doi: 10.1016/j.dam.2025.07.011
|
| [10] | X. Cheng, F. Wang, D. Z. Du, Connected dominating set, In: Encyclopedia of Algorithms, Berlin: Springer, 2016. |
| [11] |
F. Abu-Khzam, H. Fernau, B. Gras, M. Liedloff, K. Mann, Enumerating minimal connected dominating sets, SIAM J. Discr. Math., 39 (2025), 946–972. https://doi.org/10.1137/23M1611233 doi: 10.1137/23M1611233
|
| [12] | M. Fürst, D. Rautenbach, A short proof for a lower bound on the zero forcing number, Discuss. Math. Graph Theory, 40 (2020), 355–360. |
Haining Jiang, Haiyun Wan. Forcing and domination in graphs[J]. AIMS Mathematics, 2026, 11(7): 19772-19783. doi: 10.3934/math.2026802
DownLoad: