Improved Bounds For The Number of Spanning Trees of Graphs

Year 2019, Volume: 11, 31 - 39, 30.12.2019

Ezgi Kaya , Ayşe Dilek Maden

Abstract

For a given a simple connected graph, we present some new bounds via a new approach for the number of spanning trees. Usage this approach presents an advantage not only to derive old and new bounds on this topic but also gives an idea how some previous results in similar area can be developed.

Keywords

Spanning trees, normalized Laplacian eigenvalues, (degree) Kirchhoff index, Randi\'{c} index

References

• Banchev, D., Balaban, A.T., Liu, X., Klein, D.J., {\em Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances}, Int. J. Quantum Chem., \textbf{50}(1994), 2978--2981.
• Biler, P., Witkowski, A., Problems in Mathematical Analysis, New York, 1990.
• Bollobas, B., Erd\"{o}s, P., {\em Graphs of extremal weights}, Ars Combinatoria, \textbf{50}(1998), 225--233.
• Bozkurt, \c{S}.B., Bozkurt, D., {\em On the sum of powers of normalized Laplacian eigenvalues of graphs}, MATCH Commun. Math. Comput. Chem., \textbf{68}(2012), 917--930.
• Bozkurt, \c{S}. B., Bozkurt, D., {\em On the number of spanning trees of graphs}, The Scientific Worl Journal, \textbf{2014}(2014), Article ID 294038, 5 pages.
• Covers, M., Fallat, S., Kirkland, S., {\em On the normalized Laplacian energy and the general Randic index of graphs}, Linear Algebra and its Appl., \textbf{433}(2010), 172--190.
• Chen, H., Zhang, F., {\em Resistance distance and the normalized Laplacian spectrum}, Discrete App. Math., \textbf{155}(2007), 654--661.
• Chung, F.R.K., Spectral Graph Theory, CBMS Lecture Notes, Providence, 1997.
• Cvetkovi\textit{\'{c}}, D., Doob, M., Sachs, H., Spectra of Graphs, Academic Press, New York, 1980.
• Das, K.Ch., Maden, A.D., Bozkurt, \c{S}. B., {\em On the normalized Laplacian eigenvalues of graphs}, Ars Combinatoria, in press.
• Das, K.Ch., {\em A sharp upper bound for the number of spanning trees of a graph}, Graphs and Combinatorics, \textbf{23}(2007), 625--632.
• Das, K.Ch., \c{C}evik, A.S., Cang\"{u}l, I. N., {\em The number of spanning trees of a graph}, Journal of Inequalities and Applications 2013, \textbf{395}(2013), 13 pages.
• Feng, L., Yu, G., Jiang, Z., Ren, L., {\em Sharp upper bounds for the number of spanning trees of a graph}, Applicable Analysis and Discrete Mathematics, \textbf{2}(2008), 255--259.
• Grone R., Merris, R., {\em A bound for the complexity for a simple graph}, Discrete Mathematics, \textbf{69}(1988), 97--99.
• Gutman, I., Mohar, B., {\em The quasi-Wiener and the Kirchhoff indices Coincide}, J. Chem. Inf. Comput. Sci., \textbf{36}(1996), 982--985.
• Klein, D.J., Randi\textit{\'{c}}, M., {\em Resistance distance. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991)}, J. Math. Chem., \textbf{12}(1993), 81--95.
• Li, J., Shiu, W. C., Chang, A., {\em The number of spanning trees of a graph}, Applied Mathematics Letters, \textbf{23}(2010), 286--290.
• Merris, R., {\em Laplacian matrices of graphs. A Survey}, Linear Algebra and its Appl., \textbf{197}(1994), 143--176.
• Merris, R., {\em A survey of graph Laplacians}, Linear and Multilinear Algebra, \textbf{39}(1995), 19--31.
• Palacios, J., Renom, J.M., {\em Another look at the degree Kirchhoff index}, Int. J. Quantum Chem., \textbf{111}(2011), 3453--3455.
• Yang, Y.J., Jiang, X.Y.,{\em Unicyclic graphs with extremal Kirchhoff index}, MATCH Commun. Math. Comput. Chem., \textbf{60}(2008), 107--120.
• Yu, G., Feng, L., {\em Randi\'{c} index and eigenvalues of graphs}, Rocky Mount. J. Math., \textbf{40}(2010), 713--721.
• Zhang, W., Deng, H., {\em The second maximal and minimal Kirchhoff indices of unicyclic graphs}, MATCH Commun. Math. Comput. Chem., \textbf{61}(2009), 683--695.
• Zhang, X.D., {\em A new bound for the complexity of a graph}, Utilitas Mathematica, \textbf{67}(2005), 201--203.
• Zhou, B., {\em On sum of powers of the Laplacian eigenvalues of graphs}, Linear Algebra and its Appl., \textbf{429}(2008), 2239--2246.
• Zhou, B., Trinajistic, N., {\em The Kirchhoff index and the matching number}, Int. J. Quantum Chem., \textbf{109}(2009), 2978--2981.