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

Author

N. J. A. Sloane, R. K. Guy

Keywords

• nonn
• nice
• more

Comments

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

References

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

Links

• 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

Crossrefs

Cf. A212555, A097911, A348638.

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

Extensions

a(9) by Paul Tabatabai, Jul 17 2016

a(10) by Manfred Scheucher, Jan 25 2018