Notes on the harmonic index of graphs. (English) Zbl 1509.05055

Zheng, Yirong; Lv, Jian-Bo; Li, Jianxi

Rocky Mt. J. Math. 52, No. 6, 2247-2255 (2022).

The harmonic index of a graph \(G\) is defined as \(H(G)=\sum_{un\in E(G)}\frac{2}{d(u)+d(v)}\), where \(E(G)\) is the set of edges of \(G\) and \(d(u)\) is the degree of the vertex \(u\). The authors of this paper give a lower bound for \(H(G)\) in terms of \(\chi_{\mathrm{DP}}(G)\), the DP-chromatic number of \(G\). More precisely, they show that \[ H(G)\geq \frac{\chi_{\mathrm{DP}}(G)-2}{2}+\frac{2(\chi_{\mathrm{DP}}(G) -1) }{n+\chi_{\mathrm{DP}}(G)-2} +\frac{2(n- \chi_{\mathrm{DP}}(G)) }{n}, \] and this bound is sharp for all \(n\) and \(2\leq \chi_{\mathrm{DP}}(G \leq n.\) This generalizes a result by J.-B. Lv and J. Li [Discrete Appl. Math. 284, 611–615 (2020; Zbl 1443.05072)] which states that \[ H(G)\geq \frac{\chi_{\mathrm{DP}}(G)}{2}, \] and equality occurs if and only if \(G\) is a complete graph possibly with some additional isolated vertices.
Finally, they determine the structure of trees with minimum harmonic index among all trees with order \(n\) and segment \(l=(l_{1}, \dots , l_{m}). \)

Reviewer: Juan Rada (Medellín)

MSC:

05C09	Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C15	Coloring of graphs and hypergraphs

Keywords:

harmonic index; DP-chromatic number; segment sequence; tree.

Citations:

Zbl 1443.05072

Software:

GRAFFITI

References:

[1]	A. Y. Bernshteyn, A. V. Kostochka, and S. P. Pron, “On DP-coloring of graphs and multigraphs”, Sib. Math. J. 58:1 (2017), 28-36. · Zbl 1366.05038 · doi:10.1134/s0037446617010049
[2]	H. Deng, S. Balachandran, S. K. Ayyaswamy, and Y. B. Venkatakrishnan, “On the harmonic index and the chromatic number of a graph”, Discrete Appl. Math. 161:16-17 (2013), 2740-2744. · Zbl 1285.05055 · doi:10.1016/j.dam.2013.04.003
[3]	Z. Dvořák and L. Postle, “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, J. Combin. Theory Ser. B 129 (2018), 38-54. · Zbl 1379.05034 · doi:10.1016/j.jctb.2017.09.001
[4]	S. Fajtlowicz, “On conjectures of Graffiti, II”, Congr. Numer. 60 (1987), 189-197. · Zbl 0713.05054
[5]	O. Favaron, M. Mahéo, and J.-F. Saclé, “Some eigenvalue properties in graphs (conjectures of Graffiti, II)”, Discrete Math. 111:1-3 (1993), 197-220. · Zbl 0785.05065 · doi:10.1016/0012-365X(93)90156-N
[6]	I. Gutman and B. Furtula, Recent results in the theory of Randić index, Mathematical Chemistry Monographs 6, University of Kragujevac, 2008. · Zbl 1294.05002
[7]	X. Li and Y. Shi, “A survey on the Randić index”, Commun. Math. Comput. Chem. 59:1 (2008), 127-156. · Zbl 1249.05198
[8]	J. Li and W. C. Shiu, “The harmonic index of a graph”, Rocky Mountain J. Math. 44:5 (2014), 1607-1620. · Zbl 1305.05095 · doi:10.1216/RMJ-2014-44-5-1607
[9]	J. Liu, “Harmonic index of dense graphs”, Ars Combin. 120 (2015), 293-304. · Zbl 1349.05064
[10]	J.-B. Lv and J. Li, “The harmonic index of a graph and its DP-chromatic number”, Discrete Appl. Math. 284 (2020), 611-615. · Zbl 1443.05072 · doi:10.1016/j.dam.2020.03.042
[11]	M. Randic, “On characterization of molecular branching”, J. Am. Chem. Soc. 97:23 (1975), 6609-6615. · doi:10.1021/ja00856a001
[12]	X. Sun, Y. Gao, J. Du, and L. Xu, “On a conjecture of the harmonic index and the minimum degree of graphs”, Filomat 32:10 (2018), 3435-3441. · Zbl 1499.05103 · doi:10.2298/fil1810435s
[13]	B. Wu and C. Elphick, “Upper bounds for the achromatic and coloring numbers of a graph”, Discrete Appl. Math. 217:part 2 (2017), 375-380. · Zbl 1358.05120 · doi:10.1016/j.dam.2016.09.005
[14]	L. Zhong, “The harmonic index for graphs”, Appl. Math. Lett. 25:3 (2012), 561-566 · Zbl 1243.05126 · doi:10.1016/j.aml.2011.09.059