A182258 Least number k such that there exists a simple graph on k vertices having precisely n spanning trees.

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

Author

Jernej Azarija, Apr 21 2012

Keywords

• nonn

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

Examples

			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)
		

Links

• Jukka Kohonen, Table of n, a(n) for n = 3..10000
• Jernej Azarija, MathOverflow: Minimal graphs with a prescribed number of spanning trees
• 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.
• Dick Lipton, The Inverse Spanning Tree Problem
• 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.

Extensions

a(14)-a(46) from Jukka Kohonen, Feb 16 2022

a(47)-a(81) from Jukka Kohonen, Feb 17 2022