Edge forcing in tree-like architectures

Sujana, G. Jessy; Anitha, J.; Rajalaxmi, T. M.

doi:10.47974/JDMSC-2573

Open Access Research Article

Edge forcing in tree-like architectures

G. Jessy Sujanajessysug@srmist.edu.inDepartment of Computer Science and Engineering (Emerging Technologies)VadaplaniSRM Institute of Science and TechnologyChennai, Tamil Nadu, 600026, IndiaView full profile → , ^*J. AnithaCorresponding authoranithaharish78@gmail.comDepartment of MathematicsRajalakshmi Institute of TechnologyChennai, Tamil Nadu, 600124, IndiaView full profile → , T. M. Rajalaxmilaxmi.raji18@gmail.comDepartment of MathematicsSri Sivasubramaniya Nadar College of EngineeringChennai, Tamil Nadu, 603110, India0000-0001-9700-8110View full profile →

* Corresponding author · click or hover a name for details

pp. 1777–1786Vol. 29Issue 4April 2026DOI: 10.47974/JDMSC-2573 Crossmark XML

Received:: 01 May 2025
Published Online:: 08 Apr 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2573
Pages:: 1777–1786

Abstract

To create independent edges in a graph G, this work presents a variant of the zero forcing set called the ‘edge-forcing set.’ A collection of vertices in G that can influence their neighbors to force all vertices to become forced iteratively is called a zero forcing set. If a forced vertex has exactly one unforced neighbor at any given step, it forces that neighbor to become forced as well. This concept is extended to edges by the edge-forcing set. We show that figuring out the edge-forcing number, the smallest number of vertices required to build an edge-forcing set is an NP-complete task. Additionally, for a variety of tree-like structures, we investigate the edge-forcing number, giving precise values for sibling trees and defining bounds for hypertree.

Keywords

Zero forcing set Forced vertex NP-complete task Edge forcing number Unforced neighbor

Subject Classifications

05C6905C50

References

[1] K. F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevska, and B. Wissman, “Power domination and zero forcing”, arXiv:1510.02421 (2018).
[2] D. Ferrero, C. Grigorious, T. Kalinowski, J. Ryan, and S. Stephen, “Minimum rank and zero forcing number for butterfly networks”, Journal of Combinatorial Optimization, vol. 37, pp. 970–988 (2019).
[3] AIM Minimum Rank - Special Graphs Work Group, “Zero forcing sets and the minimum rank of graphs”, Linear Algebra, and its Applications, vol. 428, pp. 1628-1648 (2008).
[4] D. Burgarth and V. Giovannetti, “Full control by locally induced relaxation”, Physical Review Letters, vol. 99, pp. 1-7 (2007).
[5] D. Burgarth and K. Maruyama, “Indirect Hamiltonian identification through a small gateway”, New Journal of Physics, vol. 11, no. 103019, pp. 1-9 (2009).
[6] S. Fallat, K. Meagher, and B. Yang, “On the complexity of the positive semidefinite zero forcing number”, Linear Algebra, and its Applications, vol. 491, pp. 101-122 (2016).
[7] R. Davila and M. A. Henning, “On the total forcing number of a graph”, Discrete Applied Mathematics, vol. 257, pp. 115-127 (2019).
[8] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetneimi, and M. A. Henning, “Domination in graphs applied to electric power networks”, SIAM Journal on Discrete Mathematics, vol. 15, pp. 519- 529 (2002).
[9] R. Davila, M. A. Henning, C. Magnant, and R. Pepper, “Bounds on the Connected Forcing Number of a Graph”, Graphs and Combinatorics, vol. 34, pp. 1159–1174 (2018).
[10] D. Ferrero, S. Varghese, and A. Vijayakumar, “Power domination in honeycomb networks”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 14, pp. 521-529 (2011).
[11] D. Amos, Y. Caro, R. Davila, and R. Pepper, “Upper bounds on the k-forcing number of a graph”, Discrete Applied Mathematics, vol. 180, pp. 1-10 (2015).
[12] R. Davila and M. A. Henning, “On the Total Forcing Number of a Graph”, Discrete Applied Mathematics, vol. 257, pp. 115-127 (2019).
[13] J. Sujana, T. M. Rajalaxmi, S. Rajan, and I. Rajasingh, “Edge Forcing in Butterfly Networks”, Fundamenta Informaticae, vol. 182, no. 3, pp. 285-299 (2021).
[14] Y. Rao, S. Kosari, S. Hameed, and Z. Yousaf, “Multi-attribute decision-making using q-rung orthopair fuzzy Zagreb index”, Artificial Intelligence Review, vol. 58, no. 153, pp. 1-31 (2025).
[15] S. Kosari, X. Qiang, J. Kacprztk, Q. Ain, and H. Rashmanlou, “A Study on Topological Indices in Fuzzy Graphs with Application in Decision Making Problems”, Journal of Multiple-Valued Logic & Soft Computing, vol. 42, no. 5-6, pp. 567-589 (2024).
[16] S. Kosari, X. Shi, J. Kacprztk, Z. Chen, and H. Rashmanlou, “A Novel Description of Perfectly Regular Fuzzy Graphs with Application in Psychological Sciences”, Journal of Multiple-Valued Logic & Soft Computing, vol. 42, no. 5-6, pp. 405-412 (2024).
[17] X. Shi, S. Kosari, P. Rangasamy, R. K. Nivedhaa, and H. Rashmanlou, “Scaled aggregation operations over three-dimensional extended intuitionistic fuzzy index matrices”. Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, vol. 48, no. 1-2, pp. 123-139 (2025).
[18] S. Kosari, Z. Shao, Y. Rao, X. Liu, R. Cai, and H. Rashmanlou, “Some Types of Domination in Vague Graphs with Application in Medicine”, Journal of Multiple-Valued Logic & Soft Computing, vol. 40, no. 3-4, pp. 203-219 (2023).
[19] Z. Shao, S. Kosari, Y. Rao, H. Rashmanlou, and F. Mofidnakhaei, “New Kind of Vague Graphs with Novel Application”, Journal of Multiple-Valued Logic & Soft Computing, vol. 40 (2023).
[20] G. K. Nandini, S. Klavz ̌ar, T. M. Rajalaxmi, and R. S. Rajan, “A note on eccentricity based topological indices of honeycomb, oxide and 2-power interconnection networks”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 26, no. 1, pp. 231–253 (2023).
[21] S. Arulanand, R. S. Rajan, S. Prabhu, and S. Stephen, “Certain domination numbers for Cartesian product of graphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 3, pp. 1045–1058 (2024).
[22] G. M. Jose, K. N. Geetha, and K. Somasundaram, “Double power domination in graphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 6, pp. 2261–2278 (2025).
[23] B. S. Mahdi, J. H. H. Al-Bayati, and A. J. Al-Mahdawi, “Minimum spanning tree application in Covid-19 network structure analysis in the countries of the Middle East”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 25, no. 8, pp. 2723-2728 (2022).

Views: 156Downloads: 150Citations: 0