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 
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/
@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},
     year = {2020},
     volume = {40},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a9/
%G en
%F 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