RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2017 Issue 10, Pages 139–140 (Mi pdma366)

Applied Theory of Coding, Automata and Graphs

On the number of spanning trees in labeled cactus

V. A. Voblyi

Bauman Moscow State Technical University, Moscow

Abstract: Let $t(Ca_n(n_2,n_3,\ldots))$ be a number of spanning trees in a labelled cactus with $n$ vertices, $n_2$ be a number of its edge-blocks, $n_2\ge0$, $n_i$ be a number of its polygon-blocks with $i$ vertices, $n_i\ge0$, $i\ge3$, and $k$ be a number of cycles in this cactus. We deduce the formula $t(Ca_n(n_2,n_3,\dots))=\prod_{i\ge3}i^{n_i}$, $n\ge2$, where $n-1=n_2+2n_3+\dots$ As consequence, we obtain inequalities $t(Ca_n(n_2,n_3,\dots))\le(\frac1k(n+k-n_2-1))^k\le(\frac1k(n+k-1))^k\le e^{n-1}$.

Keywords: spanning tree, cactus, enumeration.

UDC: 519.175.3

DOI: 10.17223/2226308X/10/54



© Steklov Math. Inst. of RAS, 2025