A004401 Least number of edges in graph containing all trees on n nodes. (Formerly M0989)

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

Offset

1,3

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. 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

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

Table of n, a(n) for n=1..10.

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.

Index entries for sequences related to trees

Crossrefs

Cf. A212555, A097911, A348638.

Sequence in context: A193766 A262773 A186152 * A022819 A081527 A070978

Adjacent sequences: A004398 A004399 A004400 * A004402 A004403 A004404

Keyword

nonn,nice,more

Author

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

Extensions

a(9) by Paul Tabatabai, Jul 17 2016

a(10) by Manfred Scheucher, Jan 25 2018

Status

approved