On the maximum interval index of a graph

Abstract

For a connected graph P G on n vertices, the interval index is defined by Int(G) = {u,v} subset V(G) (|I(u, v)| - 1), where I(u, v) denotes the set of all vertices lying on a shortest u - v path. It was conjectured that, among all connected graphs on n vertices, the path Pn attains the maximum value of the interval index. In this paper we settle this conjecture, and we prove that the maximum is attained only for Pn, except for n = 4, when the cycle C4 attains the same value. We also prove that, for every n >= 31, the maximum interval index among graphs without pendant vertices equals (n^3 - n)/6 - 2(n - 4) and it is attained by a dumbbell graph, obtained by joining two 4-cycles by a path.