The minimum number of spanning trees in regular multigraphs

Jakub Pekárek ; Jean-Sébastien Sereni¹ ; Zelealem B. Yilma

¹C.N.R.S.

The electronic journal of combinatorics, Tome 29 (2022) no. 4

Résumé

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.

Détail

DOI : 10.37236/10911

Classification : 05C30, 05C05, 05C35, 05C07
Mots-clés : cubic multigraph, spanning tree, regular graph, enumeration