12 January 2016 in The Computer Journal
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.
1 January 2015 in Procedia Computer Science
Let l: V (G) →N be a labeling of the vertices of a graph G by positive integers. Define , where d(u) denotes the degree of u and N(u) denotes the open neighborhood of u. In this paper we introduce a new labeling called d-lucky labeling and study the same as a vertex coloring problem. We define a labeling l as d-lucky if c(u) ≠ c(v) , for every pair of adjacent vertices u and v in G. The d-lucky number of a graph G, denoted by ηdl(G), is the least positive k such that G has a d-lucky labeling with {1,2, ..., k} as the set of labels. We obtain ηdl(G) = 2 for hypercube network, butterfly network, benes network, mesh network, hypertree and X-tree