This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A004401 Least number of edges in graph containing all trees on n nodes. (Formerly M0989) 2
 0, 1, 2, 4, 6, 8, 11, 13, 16, 18 (list; graph; refs; listen; history; text; internal format)
 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 F. R. K. Chung, 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, 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) CROSSREFS Cf. A212555. Sequence in context: A193766 A262773 A186152 * A022819 A081527 A070978 Adjacent sequences:  A004398 A004399 A004400 * A004402 A004403 A004404 KEYWORD nonn,nice,more AUTHOR EXTENSIONS a(9) by Paul Tabatabai, Jul 17 2016 a(10) by Manfred Scheucher, Jan 25 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 21 08:16 EDT 2019. Contains 328292 sequences. (Running on oeis4.)