Geodesic
On the number of spanning trees in labeled cactus
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 139-140.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, enumeration.
Mots-clés : cactus 
@article{PDMA_2017_10_a53,
     author = {V. A. Voblyi},
     title = {On the number of spanning trees in labeled cactus},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {139--140},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a53/}
}
TY  - JOUR
AU  - V. A. Voblyi
TI  - On the number of spanning trees in labeled cactus
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 139
EP  - 140
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a53/
LA  - ru
ID  - PDMA_2017_10_a53
ER  - 
%0 Journal Article
%A V. A. Voblyi
%T On the number of spanning trees in labeled cactus
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 139-140
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a53/
%G ru
%F PDMA_2017_10_a53
V. A. Voblyi. On the number of spanning trees in labeled cactus. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 139-140. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a53/

[1] Kharari F., Palmer E., Perechislenie grafov, Mir, M., 1977, 324 pp. | MR

[2] Myrvold W., “Reliable network synthesis: some recent developments”, Combinatorics, graph theory, and algorithms, Proc. 8th Int. Conf. Graph Theory, Combinatorics, Algorithms, Appl., v. 2, 1999, 651–660 | MR

[3] Zykov F., Osnovy teorii grafov, Nauka, GRFML, M., 1987, 382 pp. | MR

[4] Tatt F., Teoriya grafov, Mir, M., 1988, 424 pp. | MR

[5] Kharari F., Teoriya grafov, Mir, M., 1973, 301 pp. | MR