A182290 Maximal number of connected graphs of order n having distinct numbers of spanning trees.

1, 1, 2, 5, 16, 65, 386, 3700, 55784, 1134526, 27053464

Offset

1,3

Comments

a(n) grows asymptotically faster than sqrt(n)*exp(2*Pi*sqrt(n/log(n))/sqrt(3)).

Links

Table of n, a(n) for n=1..11.

Jernej Azarija, Counting graphs with different numbers of spanning trees through the counting of prime partitions (preprint, 2012).

Jernej Azarija, Maximal class of simple graphs of order n with mutually distinct number of spanning trees, (Mathoverflow).

J. Sedlacek, On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.

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

Sequence in context: A369775 A268170 A000522 * A007469 A306026 A091139

Adjacent sequences: A182287 A182288 A182289 * A182291 A182292 A182293

Keyword

nonn,hard,more

Author

Jernej Azarija, Jun 27 2012

Extensions

a(11) from Jernej Azarija, Sep 07 2012

Status

approved