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.

A subset S of a connected graph G of order n is called a detour set of G if for every vertex x in G there exist vertices u; v in S such that x lie on a u – v detour path. The detour number dn( G) of a graph G is the minimum cardinality of a detour set. In this paper we compute the detour number of certain 1-fault connected planar graphs.

Average distance is an important parameter for measuring the communication cost of computer networks. A popular approach for its computation is to first partition the edge set of a network into convex components using the transitive closure of the Djoković–Winkler's relation and then to compute the average distance from the respective invariants of the components. In this article, we refine this idea further by shrinking the quotient graphs into smaller weighted graph called reduced graph, so that the average distance of the original graph is obtained from the reduced graphs. We demonstrate the significance of this technique by computing the average distance of butterfly and hypertree architectures. Along the way, a computational error from Klavžar and Nadjafi-Arani ((2014) Wiener index in weighted graphs via unification of Θ*-classes⁠, Eur. J. Combin. 36, 71–76) is corrected.

Wiener index of a graph | $G$ | is defined as | $W(G) = \frac {1}{2} \sum _{{u,v \in V(G)}} d_{{G}}(u,v)$ | . The Transmission index | $T(u)$ | of a vertex | $u$ | in a graph | $G$ | is defined as | $T(u) = \sum _{{v \in V}}d(u,v)$ | . The original technique for the computation of Wiener index was by brute-force method applying distance matrix. Later a new technique using convex partition was introduced and this convex partition method was shown to be more efficient than distance matrix method. However, this convex partition method is not universal. Some interesting architectures such as butterfly and mesh of trees do not induce convex partition. In this paper, we introduce another partition technique to accommodate larger classes of graphs which are not solved by convex partition method. This partition technique is called transmission partition method. It is different from distance matrix method and convex partition method. We show that this new technique significantly reduces the time complexity to compute the Wiener index to constant time for larger classes of graphs. We demonstrate the efficiency of this technique on butterfly networks by computing its Wiener index and its Transmission index in constant time.

The minimum linear arrangement problem is a combinatorial optimization problem whose goal is to find a linear layout of a network in such way that a certain objective cost function is optimized. In this paper, we compute the minimum linear arrangement of incomplete hypercubes using graph embeddings.

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp.