Spanning trees in a cactus
type: Item
instance of: scholarly article
title: Spanning trees in a cactus
zbMATH Open document ID: 0774.05029
DOI: 10.1016/0012-365X(92)90717-T
author: Yoshimi Egawa
author: Preben Dahl Vestergaard
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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}. \]
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 166370
zbMATH Keywords: spanning trees
zbMATH Keywords: cactus
zbMATH Keywords: rooted graph
zbMATH Keywords: lower bound
zbMATH Keywords: spanning forests
zbMATH Keywords: rooted cactus
MaRDI profile type: Publication
cites work: Q4873781
cites work: Q4187843
full work available at URL: 0012-365x(92)90717-t
OpenAlex ID: W2052971643
description: scientific article; zbMATH DE number 166370