A lower bound on the number of spanning
โ
Katherine Heinrich; Guizhen Liu
๐
Article
๐
1988
๐
John Wiley and Sons
๐
English
โ 286 KB
๐ 1 views
If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span