episciences.org_8351_1642653775
1642653775
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Fundamenta Informaticae
1875-8681
11
18
2021
Volume 182, Issue 3
Edge Forcing in Butterfly Networks
Jessy Sujana
G.
T. M.
Rajalaxmi
Indra
Rajasingh
R. Sundara
Rajan
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.
11
18
2021
8351
arXiv:2108.04764
10.3233/FI-2021-2074
https://fi.episciences.org/8351