10.3233/FI-2021-2074
G., Jessy Sujana
Jessy Sujana
G.
Rajalaxmi, T. M.
T. M.
Rajalaxmi
Rajasingh, Indra
Indra
Rajasingh
Rajan, R. Sundara
R. Sundara
Rajan
Edge Forcing in Butterfly Networks
episciences.org
2021
Mathematics - Combinatorics
contact@episciences.org
episciences.org
2021-08-11T07:46:53+02:00
2021-11-18T11:14:26+01:00
2021-11-18
eng
Journal article
https://fi.episciences.org/8351
arXiv:2108.04764
1875-8681
PDF
1
Fundamenta Informaticae ; Volume 182, Issue 3 ; 1875-8681
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.
Comment: 15 pages, 8 figures