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

1, 2, 3, 5, 8, 16, 31, 62, 129

Offset

1,2

Comments

The null subgraph is not considered to be connected.

Remarkably, a(n) = A308852(n) for all n <= 9. This cannot go on forever, however, because we have the trivial bound a(n) <= 2^n, whereas A308852(18) = 337414 > 2^18. (The upper bound below shows that already a(14) <= 7472 < A308852(14) = 8057.)

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, Diamond Graph.

Eric Weisstein's World of Mathematics, Fan Graph.

Eric Weisstein's World of Mathematics, House Graph.

Eric Weisstein's World of Mathematics, Kite Graph.

Eric Weisstein's World of Mathematics, Paw Graph.

Wikipedia, Rado graph.

Formula

a(n) <= Sum_{k=1..n} min(A001349(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. 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         1    K_1
   2         2    K_2
   3         3    K_3, P_3 (path)
   4         5    paw graph, diamond graph (K_{1,1,2})
   5         8    dart graph, kite graph, house graph, house X-graph,
                  fan graph F_{1,4}, complement of P_2 + P_3
   6        16    complement of the initial part of the Rado graph using
                  BIT predicate (the complement has House of Graphs id 25152),
                  "EEno"
   7        31    "FCvdw", "FCvfw", "FCz^g", "FEjvw"
   8        62    "GCZmp{", "GCrbU{" (House of Graphs id 36157)
   9       129    "HCpfbmn"
  10    >= 276    "INnAnDRUG" (upper bound: 319)
  11    >= 595    "JonellBani_" (upper bound: 705)
  12   >= 1304    "KonellBanibD" (upper bound: 1729)
.
For n = 4, the paw graph has 5 connected induced subgraphs: K_1, K_2, K_3, P_3, and itself. The diamond graph also has 5 connected induced subgraphs, but no 4-vertex graph has more than 5, so a(4) = 5.

Crossrefs

Cf. A001349, A308852, A370001 (not necessarily connected subgraphs), A370003.

Sequence in context: A121649 A306622 A030034 * A308852 A093000 A122630

Adjacent sequences: A369999 A370000 A370001 * A370003 A370004 A370005

Keyword

nonn,more

Author

Pontus von Brömssen, Feb 08 2024

Status

approved