Complete solution to a conjecture of Zhang-Liu-Zhou

Abstract

Let dn;m = 2n+1 and En;m be the graph obtained from a path Pdn;m+1 = v0v1:::vdn;m by joining each vertex of Kn by joining each vertex of Kn. Zhang, Liu and Zhou [On the maximal eccentric connectivity indices of graphs, Appl. Math. J. Chinese Univ., in press] conjectured that if dn;m > 3, then En;m is the graph with maximal eccentric connectivity ndex among all connected graph with n vertices and m edges. In this note, we prove this conjecture. Moreover, we present the graph with maximal eccentric connectivity index among the connected graphs with n vertices. Finally, the minimum of this graph invariant n the classes of tricyclic and tetracyclic graphs are computed.

Keywords

• Eccentric connectivity index
• tricyclic graph
• tetracyclic graph
• graph operation