Spanning trees in a cactus (Q1208370)

The paper studies spanning trees of a cactus. A cactus is a connected graph in which each block is either an edge or a circuit. A rooted graph is an ordered pair \((G,R)\), where \(G\) is a graph and \(R\) is a set of its vertices which contains exactly one vertex from each connected component of \(G\). Two rooted graphs \((G,R)\), \((G',R')\) are called isomorphic, if there exists an isomorphism of \(G\) onto \(G'\) which maps \(R\) onto \(R'\). The main result of this paper is a lower bound for the number of pairwise nonisomorphic rooted spanning forests of a graph \(G\) whose connected components are rooted cacti. In particular, for a rooted cactus \((G,R)\) of girth \(g\) with \(n\) circuits this lower bound is equal to \[ {n+\lceil g/2\rceil -1\choose \lceil g/2\rceil -1}. \]