Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

Abstract

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G = Kk ∨ (K1 + Kn - k - 1), the join of Kk, the complete graph on k vertices, with the disjoint union of K1 and Kn - k - 1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum. © 2009 Elsevier Ltd. All rights reserved.