A sharp upper bound for the number of spanning trees of a graph (Q2478168): Difference between revisions

Let \(G= (V,E)\) be a simple graph with \(n\) vertices, \(e\) edges and \(d_1\) be the largest degree. Let \(\lambda_i\), \(i = 1,2,\dots,n\) be the non-increasing eigenvalues of the Laplacian matrix of the graph \(G\). The following upper bound is established for the number of spanning trees of \(G\): \[ t(G) = \left(\frac{2e - d_1 - 1}{n-2}\right)^{n-2}. \] The equality holds if and only if \(G\) is a star or a complete graph. Earlier bounds by \textit{J. R. Grimmett} [Discrete Math. 16(1976), 323--324 (1977; Zbl 0348.05106)], \textit{R. Grone} and \textit{R. Merris} [Discrete Math. 69, 97--99 (1988; Zbl 0645.05030)], \textit{E. Nosal} [Eigenvalues of graphs. Master Thesis. Univ. Calgary (1970)], and \textit{D. M. Cvetković, M. Doob} and \textit{H. Sachs} [Spectra of graphs (1980; Zbl 0458.05042); 3rd ed. (1995; Zbl 0824.05046)]] were sharp for complete graphs only.