On a conjecture of the harmonic index and the minimum degree of graphs


Xiaoling Sun, Yubin Gao, Jianwei Du, Lan Xu




The harmonic index of a graph G is defined as the sum of the weights 2d(u)+d(v) of all edges uv of G, where d(u) denotes the degree of the vertex u in G. Cheng and Wang [4] proposed a conjecture: For all connected graphs G with n ≥ 4 vertices and minimum degree δ(G) ≥ k, where 1 ≤ k ≤ b n2 c + 1, then H(G) ≥ H(K∗k,n−k) with equality if and only if G K∗k,n−k. K∗k,n−k is a complete split graph which has only two degrees, i.e. degree k and degree n − 1, and the number of vertices of degree k is n − k, while the number of vertices of degree n − 1 is k. In this work, we prove that this conjecture is true when k ≤ n2 , and give a counterexample to show that the conjecture is not correct when k = b n2 c + 1, n is even, that is k = n2 + 1.