An All-Path Version of the Wiener Index

The Wiener index W ( G ) has originally been defined for acyclic graphs. Therefore its extension to cycle-containing structures is not unambiguous; there are several possibilities, some of which have already been realized. In this paper, we proposed an “all-path” version of W and showed that its maximal value is equal to N 2 ( N − 1)2 N -4, where N denotes the number of vertices in a graph. In contrast, the maximal values of W and its close analogues, the detour index, w ( G ), and the Szeged index, Sz ( G ), are polynomials of order 4 or less in terms of N, and therefore, it may be expected that the new version will discriminate cycle-containing structures more efficiently than W ( G ), w ( G ), or Sz ( G ).