The Minimum Number of Spanning Trees in Regular Multigraphs

Abstract

In a recent article, Bogdanowicz determines the minimum number of spanning trees a connected cubic multigraph on a fixed number of vertices can have and identifies the unique graph that attains this minimum value. He conjectures that a generalized form of this construction, which we here call a padded paddle graph, would be extremal for d-regular multigraphs where $d\geq 5$ is odd.

We prove that, indeed, the padded paddle minimises the number of spanning trees, but this is true only when the number of vertices, $n$, is greater than $(9d+6)/8$. We show that a different graph, which we here call the padded cycle, is optimal for $n<(9d+6)/8$ . This fully determines the $d$-regular multi-graphs minimising the number of spanning trees for odd values of $d$.

We employ the approach we develop to also consider and completely solve the even degree case. Here, the parity of $n$ plays a major role and we show that, apart from a handful of irregular cases when both $d$ and $n$ are small, the unique extremal graphs are padded cycles when $n$ is even and a different family, which we call fish graphs, when $n$ is odd.