On the number of spanning trees of a multi-complete/star related graph
This paper derives a closed formula for the number of spanning trees of a multi-complete/star related graph G = K-n - k(m) (a(1), a(2),..., a(l); b(1), b(2),..., b(m-1)), where K-m(a(1), a(2),..., a(l); b(1),b(2),..., bm-) consists of l complete graphs and m-l star graphs such that the ith complete graph has a(i) + 1 nodes; the jth star graph has b(j) + 1 nodes, and further, the related m roots are connected together to form a complete graph. The proposed results extend previous results to a larger graph class. In addition, we provide a general maximization theorem for the multi-star graph. (C) 2000 Elsevier Science B.V. All rights reserved.
spanning trees maximization counting combinatorial problems