On the Minimum Number of Spanning Trees in Cubic Multigraphs

Abstract

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.

Keywords

• cubic multigraph
• spanning tree
• regular graph
• enumeration
• 05c05
• 05c38