Generalized m series in tree enumeration

✍ Scribed by P.V. O'Neil

• Publisher: Elsevier Science
• Year: 1972
• Tongue: English
• Weight: 241 KB
• Volume: 294
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(72)90126-3

✦ Synopsis

Introduction

Let Kt denote the complete graph with t vertices. In (l), Bedrosian defined four classes of graphs, the p, s, r and m series, each formed by deleting certain branches of Kt. Formulas for the r and p series were first obtained by Weinberg (2) and are special cases of a formula due to the author (3).

Bedrosian , Moon (6), Bercovici (7) and Kasai et al. ( ) have obtained various expressions for the m and s series.

In this note we consider a class of graphs which contains the m series as a special case, and give a new formula for the m series itself.

ZZ. Generalization of the m Series

An m series graph is obtained from Kt by removing m branches forming a closed loop.

More generally, let M 2 3 and let PI, . . . , PM be non-empty, pairwise disjoint sets of vertices of Kt. Let Pj have kj elements, s = C& ki and T(G) be the number of labelled spanning trees in the graph G obtained by deleting from Kt the branches connecting vertices of Pi to vertices of Pi+l for 1~ i ,< M -1, and branches connecting vertices of PN to vertices of PI. When each ki = 1, G is an m series graph,

In order to determine a formula for T(G), label the vertices of G so that elements of PI are numbered 1, . . . , k,, those of P2, k, + 1, . . . , k, + k,, and so on, and the vertices of G not in IJ& Pi, s + 1, . . . , t. Form the matrix A having, for i #j, aii = -1 if i is incident with j in G, 0 otherwise and aii = degree of vertex i in G. The determinant of the t -1 by t -1 matrix obtained by removing the 4th row and column of A, for any i, gives the number of labelled trees spanning G. Now consider four cases.