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/

[1] Z.R. Bogdanowicz, Chordal 2 -connected graphs and spanning trees, J. Graph Theory 76 (2014) 224–235. doi:10.1002/jgt.21761

[2] Z.R. Bogdanowicz, On family of graphs with minimum number of spanning trees, Graphs Combin. 29 (2013) 1647–1652. doi:10.1007/s00373-012-1228-1

[3] Z.R. Bogdanowicz, Cubic graphs with minimum number of spanning trees, Ars Combin. 110 (2013) 227–238.

[4] Z.R. Bogdanowicz, Undirected simple connected graphs with minimum number of spanning trees, Discrete Math. 309 (2009) 3074–3082. doi:10.1016/j.disc.2008.08.010

[5] C.S. Cheng, Maximizing the total number of spanning trees in a graph: Two related problems in graph theory and optimum design theory, J. Combin. Theory Ser. B 31 (1981) 240–248. doi:10.1016/S0095-8956(81)80028-7

[6] A.K. Kelmans, On graphs with the maximum number of spanning trees, Random Structures Algorithms 9 (1996) 177–192. doi:10.1002/(SICI)1098-2418(199608/09)9:1/2〈177::AID-RSA11〉3.0.CO;2-L

[7] A.V. Kostochka, The number of spanning trees in graphs with a given degree sequence, Random Structures Algorithms 6 (1995) 269–274. doi:10.1002/rsa.3240060214

[8] S. Ok and C. Thomassen, On the minimum number of spanning trees in k-edge-connected graphs, J. Graph Theory 84 (2017) 286–296. doi:10.1002/jgt.22026

[9] L. Petingi and J. Rodriguez, A new technique for the characterization of graphs with a maximum number of spanning trees, Discrete Math. 244 (2002) 351–373. doi:10.1016/S0012-365X(01)00095-4