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

Author

Pontus von Brömssen, Feb 08 2024

Keywords

• nonn
• more

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.)

Examples

			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.
		

Links

• 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.

Crossrefs

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

Formula

a(n) <= Sum_{k=1..n} min(A001349(k),binomial(n,k)).