Enumeration of spanning trees of certain graphs
I M Pak, A. E. Postnikov · Russian Mathematical Surveys · 1990
In this note we give an algorithm which enables us to encode and enumerate all the spanning trees of a multipartite graph (see below). This algorithm may turn out to be useful for the enumeration of spanning trees satisfying certain conditions. The number of spanning trees of a given graph Γ without loops and without multiple edges will be denoted by_i(T). We shall consider the graphs Γ = T(G; Glt ..., Gk), where G is a graph with vertices T, 2, ..., k, and Γ is obtained from it by replacing the vertex i by G;, where, for vertices a e Gh b e Gj (i φ j), the edge (a, b) e Γ if and only if (i, j) e G.