Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Abstract

Let $\alpha (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta (n)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha (n),\beta (n)\le n$. In this paper, we show that $\alpha (n)\le \frac{n+4}{3}$ and $\beta (n)\le \frac{n+7}{3}$ if and only if $n\notin 3,4,5,6,7,9,10,13,18,22$, which is a subset of Euler's idoneal numbers. Moreover, if $n\not\equiv 2(\mathrm{mod}3)$ and $n\ne 25$ we show that $\alpha (n)\le \frac{n+9}{4}$ and $\beta (n)\le \frac{n+13}{4}.$ This improves some previously known bounds.