
arXiv: 2108.04764
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
Analysis of algorithms and problem complexity, edge-forcing set, zero forcing set, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), forced vertex, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Small world graphs, complex networks (graph-theoretic aspects), butterfly networks
Analysis of algorithms and problem complexity, edge-forcing set, zero forcing set, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), forced vertex, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Small world graphs, complex networks (graph-theoretic aspects), butterfly networks
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
