On relation between the Kirchhoff index and number of spanning trees of graph

Document Type : Original paper

Authors

1 Faculty of Electronic Engineering, Nis, Serbia

2 State University of Novi Pazar, Novi Pazar, Serbia

3 Faculty of Electronic Engineering, Nis, Srbia

Abstract

Let G be a simple connected graph with degree sequence (d1,d2,…,dn) where Δ=d1≥d2≥⋯≥dn=δ>0 and let μ1≥μ2≥⋯≥μn−1>μn=0 be the Laplacian eigenvalues of G. Let Kf(G)=n∑i=1n−11μi and τ(G)=1n∏i=1n−1μi denote the Kirchhoff index and the number of spanning trees of G, respectively. In this paper we establish several lower bounds for Kf(G) in terms of τ(G), the order, the size and maximum degree of G.

Keywords

Main Subjects

References

[1] R.B. Bapat, Resistance distance in graphs, Mathematics Student 68 (1999), 87–98.
[2] V. Cirtoaje, The best lower bound depended on two fixed variables for Jensen’s inequality with ordered variables, J. Ineq. Appl. 2010 (2010), no. 1, ID: 128258.
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 Kirchhoff index, Laplacian-energy-like invariant and Laplacian energy of graphs, Bull. Malays Math. Sci. Soc. 39 (2016), no. 1, 59–75.
[5] M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), no. 2, 298–305.
[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.
[7] P. Henrici, Two remarks on the Kantorovich inequality, Amer. Math. Montly 68 (1961), no. 9, 904–906.
[8] D.J. Klein, Resistance-distance sum rules, Croat. Chem. Acta 75 (2002), no. 2, 633–649.
[9] D.J. Klein and M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993), no. 1, 81–95.
[10] H. Kober, On the arithmetic and geometric means and on Hölder’s inequality, Proc. Amer. Math. Soc. 10 (1958), 452–459.
[11] J. Li and B. Liu, A Laplacian-energy-like invariant of a graph, MATCH Commun. Math. Comput. Chem. 59 (2008), 355–372.
[12] J. Li, W.C. Shiu, and W.H. Chan, The Laplacian spectral radius of some graphs, Croat. Chem. Acta 431 (2009), no. 1-2, 99–103.
[13] A. Lupas, A remark on the Schweitzer and Kantorovich inequalities, Univ. Beograd Publ. Electroteh. Fak. Ser. Math. Fiz. 381/409 (1972), 13–15.
[14] R. Merrtis, Laplacian matrices of graphs: a survey, Lin. Alg. Appl. 197/198 (1994), 143–176.
[15] D.S. Mitrinović, J.E. Pečarić, and A.M. Fink, Classical and new inequalities in analysis, Springer, Netherlands, 1993.
[16] D.S. Mitrinović and P.M. Vasić, Analytic inequalities, Springer Verlag, Berlin–Heidelberg–New York, 1970.
[17] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), no. 1, 17–20.
[18] W. Xiao and I. Gutman, On resistance matrices, MATCH Commun. Math. Comput. Chem. 49 (2003), 67–81.
[19] B. Zhou, I. Gutman, and T. Aleksić, A note on the Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem. 60 (2008), 441–446.
[20] B. Zhou and N. Trinajstić, A note on Kirchhoff index, Chem. Phys. Lett. 455 (2008), no. 1-3, 120–123.
[21] 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.
 
Communications in Combinatorics and Optimization
Volume 5, Issue 1
June 2020
Pages 1-8

Files

Share

How to cite

Statistics