A Few Results on Wiener Index of the kth Power of Some Specific Graphs

Abstract

For a simple connected undirected graph G = (V;E), the Wiener index W(G) of G is defined as half the sum of the shortest-path distances between all pairs of vertices u; v of G. The kth power of a graph G, denoted by Gk, is a graph with the same vertex set as G such that two vertices are adjacent in Gk if and only if their distance is at most k in G. Let Pn be a path on n vertices. In this paper, for the graph G = Pn2Pn, we obtain a closed form expression for W(G2). In addition, a correct closed form expression is stated forW (P3n). But we are unable to provide a proof forW (P3n) of how such expression has arrived. This may be compared with the existing result: for a graph G = Pn2Pn, W(G2) can be computed by an algorithm in linear time.