Improved bounds for Kirchhoff index of graphs

Document Type : Original paper


1 No

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


Let $G$ be a simple connected graph with n vertices. The Kirchhoff index of $G$ is defined as $Kf (G) = n\sum_{i=1}^{n-1}1/μ_i$, where $\mu_1\ge \mu_2\ge \dots\ge \mu_{n-1}>\mu_n=0$ are the Laplacian eigenvalues of $G$. Some bounds on $Kf (G)$ in terms of graph parameters such as the number of vertices, the number of edges, first Zagreb index, forgotten topological index, etc., are presented. These bounds improve some previously known bounds in the literature.


Main Subjects

[1] M. Bianchi, A. Cornaro, J.L. Palacios, and A. Torriero, Bounds for the Kirchho index via majorization techniques, J. Math. Chem. 51 (2013), no. 2, 569-587.
[2] P. Biler and A. Witkowski, Problems in Mathematical Analysis, CRC Press, New York, 2017.
[3] K.C. Das, A sharp upper bound for the number of spanning trees of a graph, Graphs Combin. 23 (2007), no. 6, 625-632.
[4] K.C. Das and K. Xu, On relation between Kirchho  index, Laplacian-energy-like invariant and Laplacian energy of graphs, Bull. Malays. Math. Sci. Soc. 39 (2016), no. 1, 59-75.
[5] Kinkar C Das, On the Kirchho  index of graphs, Z. Naturforschung 68a (2013), no. 8-9, 531-538.
[6] B. Furtula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015), no. 4, 1184-1190.
[7] R. Grone and R. Merris, The Laplacian spectrum of a graph ii, SIAM J. Discrete Math. 7 (1994), no. 2, 221-229.
[8] I. Gutman and B. Mohar, The quasi-Wiener and the Kirchho  indices coincide, J. Chem. Inf. Comput. Sci. 36 (1996), no. 5, 982-985.
[9] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), no. 4, 535-538.
[10] D.J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1, 81-95.
[11] J. Li, W.C. Shiu, and W.H. Chan, The laplacian spectral radius of some graphs, Linear Algebra Appl. 431 (2009), no. 1-2, 99-103.
[12] R. Merris, Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197&198 (1994), 143-176.
[13] I. Milovanović, I. Gutman, and E. Milovanović, On Kirchho  and degree Kirchho  indices, Filomat 29 (2015), no. 8, 1869-1877.
[14] I. Milovanović and E. Milovanović, Bounds of Kirchho  and degree Kirchho  indices, Bounds in Chemical Graph Theory { Mainstreams (K.C. Das, E. Milovanović, I. Milovanović, I. Gutman, B. Furtula, Ed.), Univ. Kragujevac, Kragujevac,
2017, pp. 93-119.
[15] I. Milovanović and E. Milovanović, On some lower bounds of the Kirchho  index, MATCH Commun. Math. Comput. Chem. 78 (2017), 169-180.
[16] I. Milovanović, E. Milovanović, E. Glogić, and M. Matejić, On Kirchho  index, Laplacian energy and their relations, MATCH Commun. Math. Comput. Chem. 81 (2019), no. 2, 405-418.
[17] D.S. Mitrinović and P.M. Vasić, Analytic inequalities, Springer, Berlin, 1970.
[18] B. Mohar, The Laplacian spectrum of graphs, Graph Theory, Combinatorics, and Applications (G. Alavi, O.R. Chartrand, and A.J.S. Oellermann, eds.), Wiley, New York, 1991, pp. 871-898.
[19] J.L. Palacios, Some additional bounds for the Kirchho  index, MATCH Commun. Math. Comput. Chem. 75 (2016), no. 2, 365-372.
[20] S. Pirzada, H.A. Ganie, and I. Gutman, On Laplacian-energy-like invariant and Kirchho  index, MATCH Commun. Math. Comput. Chem. 73 (2015), no. 1, 41-59.
[21] B.C. Rennie, On a class of inequalities, J. Austral. Math. Soc. 3 (1963), no. 4, 442-448.
[22] O. Rojo, R. Soto, and H. Rojo, An always nontrivial upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 312 (2000), no. 1-3, 155-159.
[23] S. Rosset, Normalized symmetric functions, Newton's inequalities, and a new set of stronger inequalities, Amer. Math. Soc. 96 (1989), no. 9, 815-819.
[24] Y. Yang, H. Zhang, and D.J. Klein, New Nordhaus-Gaddum-type results for the Kirchho  index, J. Math. Chem. 49 (2011), no. 8, 1587-1598.
[25] B. Zhou and N. Trinajstić, A note on Kirchho  index, Chem. Phys. Lett. 455 (2008), no. 1-3, 120-123.
[26] B. Zhou and N. Trinajstić, On resistance-distance and Kirchho  index., J. Math. Chem. 46 (2009), no. 1, 283-289.
[27] 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.
[28] E. Zogic and E. Glogic, A note on the Laplacian resolvent energy, Kirchho  index and their relations, Discrete Math. Lett. 2 (2019), no. 1, 32-37.
[29] P. Zumstein, Comparison of spectral methods through the adjacency matrix and the Laplacian of a graph, Th Diploma, ETH Zurich, 2005.