Affiliations: [a] Department of Computer Science and Engineering, Sri Sivasubramaniya Nadar College of Engineering, Chennai, 603 110, India. [email protected] | [b] Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering, Chennai, 603 110, India. [email protected] | [c] School of Advanced Sciences, Vellore Institute of Technology, Chennai, 600 127, India. [email protected] | [d] Department of Mathematics, Hindustan Institute of Technology and Science, Chennai, 603 103, India. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering, Chennai, 603 110, India.
Abstract: A zero forcing set is a set S of vertices of a graph G, called forced vertices of G, which are able to force the entire graph by applying the following process iteratively: At any particular instance of time, if any forced vertex has a unique unforced neighbor, it forces that neighbor. In this paper, we introduce a variant of zero forcing set that induces independent edges and name it as edge-forcing set. The minimum cardinality of an edge-forcing set is called the edge-forcing number. We prove that the edge-forcing problem of determining the edge-forcing number is NP-complete. Further, we study the edge-forcing number of butterfly networks. We obtain a lower bound on the edge-forcing number of butterfly networks and prove that this bound is tight for butterfly networks of dimensions 2, 3, 4 and 5 and obtain an upper bound for the higher dimensions.
