OFFSET
3,1
COMMENTS
The only fixed points for a(n) are 3, 4, 5, 6, 7, 10, 13, 22.
If n > 25 and n != 2 (mod 3) then a(n) <= (n+9)/4.
If n > 5 and n = 2 (mod 3) then a(n) <= (n+4)/3. [corrected by Jukka Kohonen, Feb 16 2022]
It is conjectured that a(n) = o(log(n)).
a(mn) <= a(m)+a(n)-1, by joining two graphs with m and n spanning trees at a single common vertex. - Jukka Kohonen, Feb 17 2022
LINKS
Jukka Kohonen, Table of n, a(n) for n = 3..10000
Jernej Azarija and Riste Škrekovski, Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, Mathematica Bohemica, Vol. 138 (2013), No. 2, 121--131.
Dick Lipton, The Inverse Spanning Tree Problem
Ladislav Nebeský, On the minimum number of vertices and edges in a graph with a given number of spanning trees, Časopis pro pěstování matematiky 98 (1973), 95-97.
J. Sedláček, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517.
EXAMPLE
a(100000000) = 10 since K_10 has 100000000 spanning trees.
From Jukka Kohonen, Feb 17 2022: (Start)
a(47) = 11 since the following graph has 47 spanning trees:
o-o-o-o
/ \
o--o---o--o
\ /
o--o--o
(End)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jernej Azarija, Apr 21 2012
EXTENSIONS
a(14)-a(46) from Jukka Kohonen, Feb 16 2022
a(47)-a(81) from Jukka Kohonen, Feb 17 2022
STATUS
approved