Maximizing Wiener index of graphs with fixed maximum degree

Abstract

The Wiener index of a graph is the sum of all pairwise distances of vertices of the graph. Fischermann et al [5] characterized the trees which minimize the Wiener index among all trees with the maximum degree at most Δ. They also determined the trees which maximize the Wiener index, but in a much more restricted family of trees which have two distinct vertex degrees only. In this note, we fully solve the latter problem and determine the trees which maximize the Wiener index among all graphs with the maximum degree Δ. We also determine all graphs whose Wiener index differs by less than n - Δ from the maximum value.