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

A348638 Minimal order of a graph containing as induced subgraphs isomorphic copies of all trees on n unlabeled nodes.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13

Offset: 1

James Trimble, Nov 09 2021

a(n) is the minimal order of an induced universal graph for the family of trees on n vertices.

a(9) <= 15 and a(10) <= 18 (Trimble, 2021).

James Trimble, Induced universal graphs for families of small graphs, arXiv:2109.00075 [math.CO], 2021.
James Trimble, Partitioning algorithms for induced subgraph problems, Ph.D. Thesis, Univ. of Glasgow (Scotland, 2023), 134.

Cf. A004401, A097911.

A370001 Maximum number of induced subgraphs, up to isomorphism, of an n-vertex graph.

Original entry on oeis.org

2, 3, 5, 8, 13, 23, 41, 77, 152

Offset: 1

Pontus von Brömssen, Feb 08 2024

The null subgraph is included in the counts.
A graph and its complement have the same number of induced subgraphs.
The number of terms in the n-th row of A263342 is a(n)-n.

			The table below shows all optimal graphs for n <= 9. For n = 10, a lower bound obtained by generating several thousands of random graphs is shown, together with a graph attaining this bound. Only one graph in each complementary pair is listed. If there is no known simple description or name of the optimal graphs, they are shown in the graph6 format.
   n   a(n)   optimal graphs
  ------------------------------------
   1     2    K_1 (self-complementary)
   2     3    K_2
   3     5    P_3 (path)
   4     8    paw graph
   5    13    dart graph
   6    23    initial part of the Rado graph using BIT predicate (House of Graphs id 25152)
   7    41    "FCZJw"
   8    77    "GCrbU{" (House of Graphs id 36157), "G?qjvS"
   9   152    "HPobRJm"
  10 >=312    "InLEipZiG" (upper bound: 385)
For n = 3, the path graph has 5 induced subgraphs: the null graph, K_1, K_2, the empty graph on 2 vertices, and itself. This is the maximum possible, so a(3) = 5.

House of Graphs, Graph 25152.
House of Graphs, Graph 36157.
Eric Weisstein's World of Mathematics, Dart Graph.
Eric Weisstein's World of Mathematics, Paw Graph.
Wikipedia, Rado graph.

Cf. A000088, A097911, A263342, A370002 (connected subgraphs).

a(n) <= Sum_{k=0..n} min(A000088(k),binomial(n,k)).

A370003 Least number of vertices of a universal graph for connected n-vertex graphs, i.e., a graph containing as induced subgraphs isomorphic copies of all connected n-vertex graphs.

Original entry on oeis.org

1, 2, 4, 7, 9

Offset: 1

Pontus von Brömssen, Feb 08 2024

Mathematics Stack Exchange, What is the smallest graph that contains all non-isomorphic 4-node and 5-node connected graphs as induced subgraphs?
Wikipedia, Universal graph.

Cf. A097911, A370002.

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.

A340318 Minimum size of a partial order that contains all partial orders of size n.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 16

Offset: 0

Caleb Stanford, Jan 04 2021

a(n) is the minimum number of elements in a poset P such that every poset of size n is isomorphic to a subset of P, where the subset inherits the order from P.
Elementary bounds are a(n) >= 2n-1 because it must contain a chain and an antichain, and a(n) <= 2^n-1 because every partial order embeds into the powerset partial order on n elements. It is shown in the MathOverflow link that a(n) has no polynomial upper bound. This is in particular derived from binomial(a(n),n) >= A000112(n).
a(4) = 8 verified using a computer-assisted proof with a SAT solver.
a(5) = 11 proven on MathOverflow.
a(6) = 16 and 16 <= a(7) <= 25 proven on MathOverflow. - Jukka Kohonen, Jan 15 2021

			a(2) = 3 because there are 2 nonisomorphic posets on two elements, and both embed into the poset of three elements {a, b, c} with ordering a < b (and other pairs are incomparable).
a(3) = 5 because all posets on three elements can be embedded into {a, b, c, d, e} with ordering a < d, b < c < d, and b < e.

Joel David Hamkins and Fedor Petrov, What is the minimal size of a partial order that is universal for all partial orders of size n?, MathOverflow.
Jukka Kohonen, What is the minimum size of a partial order containing all partial orders of size 5? (proofs of a(5)=11, a(6)=16 and 16 <= a(7) <= 25), MathOverflow.
Caleb Stanford, Alloy program to verify a(n) for small n, GitHub.

Cf. A000112, A001035, A004401, A097911.

# Find an u-poset that contains all n-posets as induced posets.
def find_universal_poset(n,u):
    PP = list(Posets(n))
    for U in Posets(u):
        ok = True
        for P in PP:
            if not U.has_isomorphic_subposet(P):
                ok = False
                break
        if ok:
            return U
    return None

a(6) from Jukka Kohonen, Jan 15 2021

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

A348638 Minimal order of a graph containing as induced subgraphs isomorphic copies of all trees on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A370001 Maximum number of induced subgraphs, up to isomorphism, of an n-vertex graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A370003 Least number of vertices of a universal graph for connected n-vertex graphs, i.e., a graph containing as induced subgraphs isomorphic copies of all connected n-vertex graphs.

Views

Author

Keywords

Links

Crossrefs

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A340318 Minimum size of a partial order that contains all partial orders of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Extensions