Authors: Z.R. Bogdanowicz Title: On the minimum number of spanning trees in cubic multigraphs Source: Discussiones Mathematicae Graph Theory Received 18.10.2016, Revised 20.02.2018, Accepted 21.02.2018, doi: 10.7151/dmgt.2123 | |
Abstract: Let G_{2n}, H_{2n} be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G_{2n}), t(H_{2n}) denote the number of spanning trees in G_{2n}, H_{2n}, respectively. We prove that for n ≥ 3 there is the unique G_{2n} such that t(G_{2n}) < t(H_{2n}) for any H_{2n}. Furthermore, we prove that such a graph has t(G_{2n}) = 5^{2}2^{n-3} spanning trees. Based on our results we give a conjecture for the unique r-regular connected graph H_{2n} of order 2n and odd degree r that minimizes the number of spanning trees. | |
Keywords: cubic multigraph, spanning tree, regular graph, enumeration | |
Links: |