|
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.
Citation:
V. A. Voblyi, “On the number of spanning trees in labeled cactus”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 139–140
Linking options:
https://www.mathnet.ru/eng/pdma366 https://www.mathnet.ru/eng/pdma/y2017/i10/p139
|
Statistics & downloads: |
Abstract page: | 154 | Full-text PDF : | 51 | References: | 39 |
|