The minimum number of spanning trees in regular multigraphs (Q2112560)

Summary: In a recent article, \textit{Z. R. Bogdanowicz} [Discuss. Math., Graph Theory 40, No. 1, 149--159 (2020; Zbl 1430.05013)] 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\geqslant 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 \(\frac{9d+6}{8}\). We show that a different graph, which we here call the padded cycle, is optimal for \(n<\frac{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.