On the hyper-Wiener index of cacti

Abstract

Let G be a simple connected graph. The hyper-Wiener index WW(G) is defined as WW(G) = 1/2Σ_{u,v}⊆v(G)(d(u,v) + d²(u,v)), with the summation going over all pairs of vertices in G. A graph G is called a cactus if each block of G is either an edge or a cycle. Denote by Cat(n,t) the set of connected cacti possessing n vertices and t cycles. In this paper, we obtain the smallest hyper-Wiener indices among graphs in Cat(n, t), we also determine the corresponding extremal graph.