2012/10/23 by Jernej Azarija, Azarija, Jernej, Riste Škrekovski +1 · 1 citation
Mathematics · #Graph theory and applications #math.CO
paper · pdf · doi:10.48550/arxiv.1210.6335
arxiv created 2013/02/11 · arxiv updated 2013/02/12
Let α(n) be the least number k for which there exists a simple graph with k vertices having precisely n ≥ 3 spanning trees. Similarly, define β(n) as the least number k for which there exists a simple graph with k edges having precisely n ≥ 3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that α(n),β(n) ≤ n. In this paper, we show that α(n) ≤ (n+4)/(3) and β(n) ≤ (n+7)/(3) if and only if n ∉ 3,4,5,6,7,9,10,13,18,22, which is a subset of Euler's idoneal numbers. Moreover, if n \not ≡ 2 \pmod3 and n \not = 25 we show that α(n) ≤ (n+9)/(4) and β(n) ≤ (n+13)/(4). This improves some previously known bounds.