cp's OEIS Frontend

A004401 Least number of edges in graph containing all trees on n nodes.

%I A004401 M0989 #58 Jan 31 2025 11:39:31
%S A004401 0,1,2,4,6,8,11,13,16,18
%N A004401 Least number of edges in graph containing all trees on n nodes.
%C A004401 _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. Eqn. 3 and Related Question 1 in Chung and Graham). 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
%C A004401 Chung and Graham use n and T_n to refer to trees on n *edges* (i.e., n-1 nodes). - _Eric W. Weisstein_, Jan 30 2025
%C A004401 Graphs containing all trees on n nodes could be referred to as fully n-forested graphs. - _Eric W. Weisstein_, Jan 31 2025
%D A004401 R. L. Graham, personal communication.
%D A004401 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A004401 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 A004401 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 A004401 Manfred Scheucher, <a href="/A004401/a004401_1.sage.txt">Sage Program</a>
%H A004401 Manfred Scheucher, <a href="/A004401/a004401_1.png">Graph on 10 vertices and 18 edges containing all trees on 10 vertices.</a>
%H A004401 Paul Tabatabai, <a href="/A004401/a004401.sage.txt">Exhaustive search proving a(9) = 16. (Sage script)</a>
%H A004401 Paul Tabatabai, <a href="/A004401/a004401.png">Graph on 9 vertices and 16 edges containing all trees on 9 vertices.</a>
%H A004401 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FullyForestedGraph.html">Fully Forested Graph</a>.
%H A004401 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%Y A004401 Cf. A212555, A097911, A348638.
%Y A004401 Cf. A380740 (numbers of smallest fully forested graphs).
%K A004401 nonn,nice,more
%O A004401 1,3
%A A004401 _N. J. A. Sloane_, _R. K. Guy_
%E A004401 a(9) by _Paul Tabatabai_, Jul 17 2016
%E A004401 a(10) by _Manfred Scheucher_, Jan 25 2018