|
%I M0989 #49 Nov 19 2021 16:45:44
%S 0,1,2,4,6,8,11,13,16,18
%N Least number of edges in graph containing all trees on n nodes.
%C _Paul Tabatabai_'s program only tests graphs on n nodes, but the term a(9) = 16 is now confirmed. It seems to be sufficient to test only graphs on n vertices (cf. Related Questions, Question 1 in Chung, Graham, and Pippenger). Moreover, if this assumption is true, then the next terms are a(11) = 22 and a(12) = 24. Also note that my program can be used to enumerate all possible solutions. - _Manfred Scheucher_, Jan 25 2018
%D R. L. Graham, personal communication.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H F. R. K. Chung and R. L. Graham, <a href="http://dx.doi.org/10.1016/0095-8956(78)90072-2">On graphs which contain all small trees</a>, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 14--23. MR0505812 (58 #21808a)
%H F. R. K. Chung, R. L. Graham and N. Pippenger, <a href="http://scholarship.claremont.edu/hmc_fac_pub/1042/">On graphs which contain all small trees. II</a>. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pp. 213-223. Colloq. Math. Soc. Janos Bolyai, 18. North-Holland, Amsterdam, 1978.
%H Manfred Scheucher, <a href="/A004401/a004401_1.sage.txt">Sage Program</a>
%H Manfred Scheucher, <a href="/A004401/a004401_1.png">Graph on 10 vertices and 18 edges containing all trees on 10 vertices.</a>
%H Paul Tabatabai, <a href="/A004401/a004401.sage.txt">Exhaustive search proving a(9) = 16. (Sage script)</a>
%H Paul Tabatabai, <a href="/A004401/a004401.png">Graph on 9 vertices and 16 edges containing all trees on 9 vertices.</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%Y Cf. A212555, A097911, A348638.
%K nonn,nice,more
%O 1,3
%A _N. J. A. Sloane_, _R. K. Guy_
%E a(9) by _Paul Tabatabai_, Jul 17 2016
%E a(10) by _Manfred Scheucher_, Jan 25 2018
|
