cp's OEIS Frontend

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

%I A182258 #43 Jun 10 2022 06:15:28
%S A182258 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,
%T A182258 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,
%U A182258 7,6,8,9,7,7,9,5,7,9,9,7,7,6
%N A182258 Least number k such that there exists a simple graph on k vertices having precisely n spanning trees.
%C A182258 The only fixed points for a(n) are 3, 4, 5, 6, 7, 10, 13, 22.
%C A182258 If n > 25 and n != 2 (mod 3) then a(n) <= (n+9)/4.
%C A182258 If n > 5 and n = 2 (mod 3) then a(n) <= (n+4)/3. [corrected by _Jukka Kohonen_, Feb 16 2022]
%C A182258 It is conjectured that a(n) = o(log(n)).
%C A182258 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
%H A182258 Jukka Kohonen, <a href="/A182258/b182258.txt">Table of n, a(n) for n = 3..10000</a>
%H A182258 Jernej Azarija, <a href="http://mathoverflow.net/questions/93656">MathOverflow: Minimal graphs with a prescribed number of spanning trees</a>
%H A182258 Jernej Azarija and Riste Škrekovski, <a href="http://dml.cz/dmlcz/143285">Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees</a>, Mathematica Bohemica, Vol. 138 (2013), No. 2, 121--131.
%H A182258 Dick Lipton, <a href="http://rjlipton.wordpress.com/2009/06/24/the-inverse-spanning-tree-problem/">The Inverse Spanning Tree Problem</a>
%H A182258 Ladislav Nebeský, <a href="http://dml.cz/dmlcz/117780">On the minimum number of vertices and edges in a graph with a given number of spanning trees</a>, Časopis pro pěstování matematiky 98 (1973), 95-97.
%H A182258 J. Sedláček, <a href="http://dx.doi.org/10.4153/CMB-1970-093-0">On the minimal graph with a given number of spanning trees</a>, Canad. Math. Bull. 13 (1970) 515-517.
%e A182258 a(100000000) = 10 since K_10 has 100000000 spanning trees.
%e A182258 From _Jukka Kohonen_, Feb 17 2022: (Start)
%e A182258 a(47) = 11 since the following graph has 47 spanning trees:
%e A182258     o-o-o-o
%e A182258    /       \
%e A182258   o--o---o--o
%e A182258    \       /
%e A182258     o--o--o
%e A182258 (End)
%K A182258 nonn
%O A182258 3,1
%A A182258 _Jernej Azarija_, Apr 21 2012
%E A182258 a(14)-a(46) from _Jukka Kohonen_, Feb 16 2022
%E A182258 a(47)-a(81) from _Jukka Kohonen_, Feb 17 2022