Using a new labeling technique and matrix computations, this paper derives a closed formula for the number of spanning trees of a multi-star related graph G = Kn - Km(al, ~22, . . , a,), where Km(al, q, . . , am) consists of m star graphs such that the ith one has a root node connected to ai leaves, and further, the m roots are connected together to form a complete graph. This result generalizes the previous result by Nikolopoulos and Rondogiannis (1998) which is limited to m = 2,3,4. 0 1998 Elsevier Science B.V. All rights reserved.
['Wen-Ming Yan', 'Wendy J. Myrvold', 'Kuo-Liang Chung']
A formula for the number of spanning trees of a multi-star related graph