Premium
A lower bound on the number of spanning trees with k end‐vertices
Author(s) -
Heinrich Katherine,
Liu Guizhen
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120110
Subject(s) - combinatorics , mathematics , spanning tree , minimum degree spanning tree , wheel graph , upper and lower bounds , graph , integer (computer science) , path graph , discrete mathematics , graph power , line graph , computer science , mathematical analysis , programming language
If a graph G with cycle rank ρ contains both spanning trees with m and with n end‐vertices, m < n , then G has at least 2ρ spanning trees with k end‐vertices for each integer k, m < k < n. Moreover, the lower bound of 2 ρ is best possible.