Trees with the maximal value of Graovac–Pisanski index

摘要

Let G be a graph. The Graovac–Pisanski index is defined as GP(G)=|V(G)|2|Aut(G)|∑u∈V(G)∑α∈Aut(G)dG(u,α(u)), where Aut(G) is the group of automorphisms of G. This index is considered to be an extension of the original Wiener index, since it takes into account not only the distances, but also the symmetries of the graph. In this paper, for each n we find all trees on n vertices with the maximal value of Graovac–Pisanski index. With the exception of several small values of n, there are exactly two extremal trees, one of them being the path.