|
|
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:
o-o-o-o
/ \
o--o---o--o
\ /
o--o--o
(End)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|