Complete solution to a conjecture of Zhang-Liu-Zhou

Abstract

Let dn,m =2n+1− √ 17+8(m−n) 2 and En,m be the graph obtained from a path Pdn,m+1 = v0v1 · · · vdn,m by joining each vertex of Kn−dn,m−1 to vdn,m and vdn,m−1, and by joining m − n + 1 − n−dn,m 2 vertices of Kn−dn,m−1 to vdn,m−2 . 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 index 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 in the classes of tricyclic and tetracyclic graphs are computed.