Spanning trees in a cactus (Q1208370)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spanning trees in a cactus |
scientific article |
Statements
Spanning trees in a cactus (English)
0 references
16 May 1993
0 references
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}. \]
0 references
spanning trees
0 references
cactus
0 references
rooted graph
0 references
lower bound
0 references
spanning forests
0 references
rooted cactus
0 references