On the minimum number of spanning trees in cubic multigraphs
Discussiones Mathematicae Graph Theory
Received 18.10.2016, Revised 20.02.2018, Accepted 21.02.2018, doi: 10.7151/dmgt.2123
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) < 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.
cubic multigraph, spanning tree, regular graph, enumeration