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 $(d_1,d_2,\ldots, d_n)$ where $\Delta =d_1\geq d_2\geq\cdots\geq d_n=\delta >0$ and let $\mu_1\geq \mu_2\geq\cdots\geq\mu_{n-1}>\mu_n=0$ be the Laplacian eigenvalues of $G$. Let $Kf(G)=n\sum_{i=1}^{n-1} \frac{1}{\mu_i}$ and $\tau(G)=\frac 1n \prod_{i=1}^{n-1} \mu_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 $\tau(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