A Sharp Upper Bound for the Number of Spanning Trees of a Graph |
| |
Authors: | Kinkar Ch Das |
| |
Institution: | (1) Université Paris-XI, Orsay, LRI, Batiment 490, 91405 Orsay Cedex, France |
| |
Abstract: | Let G = (V,E) be a simple graph with n vertices, e edges and d1 be the highest degree. Further let λi, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ2 = λ3 = ... = λn-1 if and only if G is a complete graph or a star graph or a (d1,d1) complete bipartite graph.
Also we establish the following upper bound for the number of spanning trees of G on n, e and d1 only:
The equality holds if and only if G is a star graph or a complete graph. Earlier bounds by Grimmett 5], Grone and Merris 6], Nosal 11], and Kelmans 2] were
sharp for complete graphs only. Also our bound depends on n, e and d1 only.
This work was done while the author was doing postdoctoral research in LRI, Université Paris-XI, Orsay, France. |
| |
Keywords: | Graph spanning trees Laplacian matrix |
本文献已被 SpringerLink 等数据库收录! |
|