Some lower bounds on the Kirchhoff index

Document Type : Original paper

Authors

Faculty of Electronic Engineering, University of Niš, Niš, Serbia

Abstract

Let $G=(V,E)$, $V=\{v_1,v_2,\ldots,v_n\}$, $E=\{e_1,e_2,\ldots, e_m\}$, be a simple graph of order $n\ge 2$ and size $m$ without isolated vertices. Denote with $\mu_1\ge \mu_2\ge \cdots \ge \mu_{n-1}>\mu_n=0$ the Laplacian eigenvalues of $G$. The Kirchhoff index of a graph $G$,  defined in terms of Laplacian eigenvalues, is given as $Kf(G) = n \sum_{i=1}^{n-1}\frac{1}{\mu_i}$. Some new lower bounds on $Kf(G)$ are obtained.

Keywords

Main Subjects


[1] Ş.B. Bozkurt Altındağ, M. Matejić, I. Milovanović, and E. Milovanović, Improved bounds for Kirchhoff index of graphs, Commun. Comb. Optim. 8 (2023), no. 1, 243–251.
https://doi.org/10.22049/cco.2022.27492.1275
[2] V. Cirtoaje, The best lower bound depended on two fixed variables for Jensen’s inequality with ordered variables, J. Ineq. Appl. 2010 (2010), Article ID: 128258.
https://doi.org/10.1155/2010/128258
[3] K.C. Das and I. Gutman, On Laplacian energy, Laplacian-energy-like invariant and Kirchhoff index of graphs, Linear Algebra Appl 554 (2018), 170–184.
https://doi.org/10.1016/j.laa.2018.05.030
[4] K.C. Das and I. Gutman, Comparing Laplacian energy and Kirchhoff index, MATCH Commun. Math. Comput. Chem. 81 (2019), no. 2, 419–424.
[5] I. Gutman, K.C. Das, B. Furtula, E. Milovanović, and I. Milovanović, Generalizations of Szökefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory, Applied Math. Comput. 313 (2017), 235–244.
https://doi.org/10.1016/j.amc.2017.05.064
[6] I. Gutman and B. Mohar, The quasi-Wiener and the Kirchhoff indices coincide, J. Chem. Inf. Comput. Sci. 36 (1996), no. 5, 982–985.
https://doi.org/10.1021/ci960007t
[7] J.L.W.V. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Math. 30 (1906), no. 1, 175–193.
https://doi.org/10.1007/BF02418571
[8] D.J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1, 81–95.
https://doi.org/10.1007/BF01164627
[9] M. Matejić, E. Milovanović, P.D. Milošević, and I. Milovanović, A note on the Kirchhoff index of graphs, Open J. Discr. Appl. Math. 2 (2019), no. 3, 1–6.
https://doi.org/10.30538/psrp-odam2019.0017
[10] E. Milovanović, I. Milovanović, and M. Matejić, On relation between the Kirchhoff index and Laplacian-energy-like invariant of graphs, Math. Inter. Research 2 (2017), no. 2, 141–154.
https://doi.org/10.22052/mir.2017.85687.1063
[11] I. Milovanović and E. Milovanović, Bounds of Kirchhoff and degree Kirchhoff indices, Bounds in Chemical graph theory – Mainstreams (I. Gutman, B. Furtula, K.C. Das, E. Milovanovi´c, and I. Milovanovi´c, eds.), Univ. Kragujevac, Kraguje-
vac, 2017, pp. 93–119.
[12] I. Milovanović and E. Milovanović, On some lower bounds of the Kirchhoff index, MATCH Commun. Math. Comput. Chem. 78 (2017), no. 1, 169–180.
[13] I. Milovanović, E. Milovanović, E. Glogić, and M. Matejić, On Kirchhoff index, Laplacian energy and their relations, MATCH Commun. Math. Comput. Chem. 81 (2019), no. 2, 405–418.
[14] D.S. Mitrinovic, J. Pecaric, and A.M. Fink, Classical and new inequalities in analysis, Kluwer Academic Publishers, Dordrecht, 1993.
[15] J.L. Palacios, Some additional bounds for the Kirchhoff index, MATCH Commun. Math. Comput. Chem. 75 (2016), no. 2, 365–372.
[16] J.V. Szökefalvi Nagy, Über algebraishe gleichungen mit lauter reellen wurzeln, Jahresbericht der deutschen Mathematiker – Vereingung 24 (1918), 37–43.
[17] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), no. 1, 17–20.
https://doi.org/10.1021/ja01193a005
[18] B. Zhou and N. Trinajstić, A note on Kirchhoff index, Chem. Phys. Lett. 455 (2008), no. 1-3, 120–123.
https://doi.org/10.1016/j.cplett.2008.02.060
[19] H.Y. Zhu, D.J. Klein, and I. Lukovits, Extensions of the Wiener number, J. Chem. Inf. Comput. Sci. 36 (1996), no. 3, 420–428.
https://doi.org/10.1021/ci950116s