Graphs with a given conditional diameter that maximize the Wiener index

Abstract

The Wiener index $ W(G) $ of a graph $ G $ is one of the most well-known topological indices, which is defined as the sum of distances between all pairs of vertices of $ G $. The diameter $ D(G) $ of $ G $ is the maximum distance between all pairs of vertices of $ G $, and the conditional diameter $ D(G; s) $ is the maximum distance between all pairs of vertex subsets with cardinality $ s $ of $ G $. When $ s = 1 $, the conditional diameter $ D(G; s) $ is just the diameter $ D(G) $. The authors in [18] characterized the graphs with the maximum Wiener index among all graphs with diameter $ D(G) = n-c $, where $ 1\le c\le 4 $. In this paper, we will characterize the graphs with the maximum Wiener index among all graphs with conditional diameter $ D(G; s) = n-2s-c $ ($ -1\leq c\leq 1 $), which extends partial results above.

Keywords

• wiener index
• diameter
• conditional diameter