Solution to the minimum harmonic index of graphs with given minimum degree

Document Type : Research Paper


Guangdong University of Foreign Studies


The harmonic index of a graph $G$ is defined as $ H(G)=\sum\limits_{uv\in E(G)}\frac{2}{d(u)+d(v)}$‎, ‎where $d(u)$ denotes the degree of a vertex $u$ in $G$‎. ‎Let $\mathcal{G}(n,k)$ be the set of simple $n$-vertex graphs with minimum degree at least $k$‎. ‎In this work we consider the problem of determining the minimum value of the‎ ‎harmonic index and the corresponding extremal graphs among $\mathcal{G}(n,k)$‎. ‎We solve the problem for each integer $k (1\le k\le n/2)$ and show the corresponding extremal graph is the complete split graph $K_{k,n-k}^*$‎. ‎This result together with our previous result which solve the problem for each integer $k (n/2 \le k\le n-1)$ give a complete solution of the problem‎.


Main Subjects

[1] O. Favaron, M. Mahó and J.F. Saclé, Some eigenvalue properties in graphs (conjectures of Graffiti-II), Discrete Math., 111 (1993) 197–220.
[2] J. Liu, Harmonic index of dense graphs, Ars Combinatoria, 120 (2015) 293–304.
[3] L. Lovász, Combinatorial problems and exercises, Akadémiai Kiadó, Budapest, 1979.
[4] X. Li and I. Gutman, Mathematical Aspects of Randic-Type Molecular Structure Descriptors, Mathematical Chem-istry Monographs, Kragujevac, (2006) pp. VI+330.
[5] X. Li and Y. T. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem., 59 (2008) 127–156.
[6] B. Lucic, N. Trinajstic and B. Zhou, Comparison between the sum-connectivity index and product-connectivity index for benzenoid hydrocarbons, Chem. Phys. Lett., 475 (2009) 146–148.
[7] R. Wu, Z. Tang and H. Deng, A lower bound for the harmonic index of a graph with minimum degree at least two, Filomat, 27 (2013) 51–55.
[8] L. Zhong, The harmonic index for graphs, Appl. Math. Lett., 25 (2012) 561–566.
[9] L. Zhong, The harmonic index on unicyclic graphs, Ars Combin., 104 (2012) 261–269.