login
A182258
Least number k such that there exists a simple graph on k vertices having precisely n spanning trees.
1
3, 4, 5, 6, 7, 4, 5, 10, 5, 5, 13, 6, 6, 4, 7, 8, 7, 5, 5, 22, 8, 5, 9, 8, 7, 6, 6, 6, 9, 6, 7, 10, 6, 6, 7, 10, 7, 5, 7, 8, 7, 7, 5, 7, 11, 6, 7, 7, 7, 6, 8, 6, 6, 6, 8, 8, 8, 6, 6, 9, 7, 6, 8, 6, 8, 7, 6, 8, 9, 7, 7, 9, 5, 7, 9, 9, 7, 7, 6
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
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.
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
Sequence in context: A111608 A126800 A245689 * A067628 A168093 A095254
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