A348638 -id:A348638 - 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

A370301 Least number of vertices of a universal graph for cycles up to length n, i.e., a graph containing induced cycles of lengths 3..n.

Original entry on oeis.org

3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16

Offset: 3

Pontus von Brömssen, Feb 14 2024

			In the following table, graphs with a(n) vertices and induced cycles of lengths 3..n are shown. The vertices 1, 2, ..., n constitute an induced cycle; only the additional vertices n+1, ..., a(n) and their lists of neighbors are given.
   n | a(n) | vertices outside the given induced n-cycle and their neighbors
  ---+------+---------------------------------------------------------------
   3 |   3  | none
   4 |   5  | 5:1,2
   5 |   6  | 6:1,2,4
   6 |   7  | 7:1,2,4
   7 |   9  | 8:1,2,4,9; 9:6,8
   8 |  10  | 9:1,3,4,10; 10:6,9
   9 |  11  | 10:1,5,11; 11:2,5,10
  10 |  12  | 11:1,2,4,7; 12:6,9
  11 |  13  | 12:1,2,5,6,8; 13:3,11
  12 |  14  | 13:1,2,5,7; 14:3,6,8
  13 |  16  | 14:1,3,4,7,15; 15:10,14; 16:6,9
For n = 7, the graph with a cycle 1-2-...-7-1 and two additional vertices with edges 8-1, 8-2, 8-4, 8-9, and 9-6 contains induced cycles of lengths 3..7: 1-2-8-1, 2-3-4-8-2, 1-7-6-9-8-1 (for example), 1-7-6-5-4-8-1, and 1-2-3-4-5-6-7-1. No such graph with fewer vertices exists, so a(7) = 9.

Wikipedia, Universal graph.

Cf. A097911, A348638, A370003, A370302.

a(n) = A370302(2^(n-2)-1).

a(n) <= a(n-1) + 2.

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