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

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

Offset

1,1

Comments

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.

Links

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

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.

Formula

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

Example

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.

Crossrefs

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

Sequence in context: A068202 A096796 A257418 * A125730 A340708 A074030

Adjacent sequences: A369998 A369999 A370000 * A370002 A370003 A370004

Keyword

nonn,more

Author

Pontus von Brömssen, Feb 08 2024

Status

approved