A212555 -id:A212555 - cp's OEIS frontend

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

0, 1, 2, 4, 6, 8, 11, 13, 16, 18

Offset: 1

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
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
Graphs containing all trees on n nodes could be referred to as fully n-forested graphs. - Eric W. Weisstein, Jan 31 2025

R. L. Graham, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

F. R. K. Chung and R. L. Graham, On graphs which contain all small trees, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 14--23. MR0505812 (58 #21808a)
F. R. K. Chung, R. L. Graham and N. Pippenger, On graphs which contain all small trees. II. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pp. 213-223. Colloq. Math. Soc. Janos Bolyai, 18. North-Holland, Amsterdam, 1978.
Manfred Scheucher, Sage Program
Manfred Scheucher, Graph on 10 vertices and 18 edges containing all trees on 10 vertices.
Paul Tabatabai, Exhaustive search proving a(9) = 16. (Sage script)
Paul Tabatabai, Graph on 9 vertices and 16 edges containing all trees on 9 vertices.
Eric Weisstein's World of Mathematics, Fully Forested Graph.
Index entries for sequences related to trees

Cf. A212555, A097911, A348638.

Cf. A380740 (numbers of smallest fully forested graphs).

a(9) by Paul Tabatabai, Jul 17 2016

a(10) by Manfred Scheucher, Jan 25 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions