

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



EXAMPLE

a(100000000) = 10 since K_10 has 100000000 spanning trees.
a(47) = 11 since the following graph has 47 spanning trees:
oooo
/ \
oooo
\ /
ooo
(End)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



