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.