An algorithm on the Wiener polarity index of bipartite graphs

Abstract

The Wiener polarity index of a graph $G$ is the number of unordered pairs of vertices $u,v$ such that the distance between $u$ and $v$ is three, which was introduced by Harold Wiener in 1947. A linear time algorithm for computing the Wiener polarity index of trees was described, and also an algorithm which computes the index $W_p(G)$ for any given connected graph $G$ on $n$ vertices in time $O(M(n))$ was presented, where $M(n)$ denotes the time necessary to multiply two $n\times n$ matrices of small integers (which is currently known to be $O(n^{2.376})$). In this paper, we establish one polynomial algorithm to calculate the value of the Wiener polarity index of a bipartite graph.