

A004401


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


2




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, R. L. Graham, On graphs which contain all small trees, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 1423. 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. 213223. Colloq. Math. Soc. Janos Bolyai, 18. NorthHolland, 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.
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



