Jessy Sujana G. ; T. M. Rajalaxmi ; Indra Rajasingh ; R. Sundara Rajan - Edge Forcing in Butterfly Networks

fi:8351 - Fundamenta Informaticae, November 18, 2021, Volume 182, Issue 3 - https://doi.org/10.3233/FI-2021-2074
Edge Forcing in Butterfly Networks

Authors: 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.


Volume: Volume 182, Issue 3
Published on: November 18, 2021
Accepted on: August 23, 2021
Submitted on: August 11, 2021
Keywords: Mathematics - Combinatorics


Share

Consultation statistics

This page has been seen 31 times.
This article's PDF has been downloaded 10 times.