Geodesic
On the Minimum Number of Spanning Trees in Cubic Multigraphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 149-159

Voir la notice de l'article provenant de la source Library of Science

Let G2n, H2n be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G2n), t (H2n) denote the number of spanning trees in G2n, H2n, respectively. We prove that for n ≥ 3 there is the unique G2n such that t(G2n) lt; t(H2n) for any H2n. Furthermore, we prove that such a graph has t(G2n) = 522n−3 spanning trees. Based on our results we give a conjecture for the unique r-regular connected graph H2n of order 2n and odd degree r that minimizes the number of spanning trees.
Keywords: cubic multigraph, spanning tree, regular graph, enumeration 
@article{DMGT_2020_40_1_a9,
     author = {Bogdanowicz, Zbigniew R.},
     title = {On the {Minimum} {Number} of {Spanning} {Trees} in {Cubic} {Multigraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {149--159},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a9/}
}
TY  - JOUR
AU  - Bogdanowicz, Zbigniew R.
TI  - On the Minimum Number of Spanning Trees in Cubic Multigraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 149
EP  - 159
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a9/
LA  - en
ID  - DMGT_2020_40_1_a9
ER  - 
%0 Journal Article
%A Bogdanowicz, Zbigniew R.
%T On the Minimum Number of Spanning Trees in Cubic Multigraphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 149-159
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a9/
%G en
%F DMGT_2020_40_1_a9
Bogdanowicz, Zbigniew R. On the Minimum Number of Spanning Trees in Cubic Multigraphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 149-159. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a9/