|
|
A182290
|
|
Maximal number of connected graphs of order n having distinct numbers of spanning trees.
|
|
0
|
|
|
1, 1, 2, 5, 16, 65, 386, 3700, 55784, 1134526, 27053464
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
a(n) grows asymptotically faster than sqrt(n)*exp(2*Pi*sqrt(n/log(n))/sqrt(3)).
|
|
LINKS
|
|
|
EXAMPLE
|
a(3) = 2 since any connected graph on 3 vertices can either have 1 spanning tree (any tree) or 3 (triangle).
|
|
PROG
|
(Sage) # needs the package nauty:
len( set([g.spanning_trees_count() for g in graphs.nauty_geng('-c ' + str(n)) ]))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|