Computing Wiener Index of (Pn Box Pn)2

摘要

Given a simple connected undirected graph $G$ = ($V$, $E$), the $Wiener$ $index$ $W$($G$) of $G$ is defined as half the sum of the distances of the form $d(u, v)$ between all pairs of vertices $u, v$ of $G$, where $d(u, v)$ denotes the distance of a shortest $u-v$ path in $G$. The $k$th power of a graph $G$, denoted by $G^k$, is a graph with the same vertex set as $G$ such that two vertices are adjacent in $G^k$ if and only if their distance is at most $k$ in $G$. We first outline an algorithm for computing $W(P^k_n Box P^k_n)$ in linear time. Then we obtain an expression for $W((P_n Box P_n)^2)$. This suggests an algorithm for computing $W((P_n Box P_n)^2)$ in linear time. This may be compared with the existing result: for a graph $G$ with $v$ vertices and $e$ edges, $W(G)$ can be computed by an algorithm in time $O(ve)$.