A308852 -id:A308852 - cp's OEIS frontend

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

Pontus von Brömssen, Feb 08 2024

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

			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.

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.

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

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

A343491 Number of representations of n! as a sum of 3 tetrahedral numbers (A000292).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 1, 3, 5, 2, 3, 6, 5, 8, 8, 7, 2, 7, 8, 3, 11, 2, 2

Offset: 1

Altug Alkan, Apr 17 2021

Conjecture I: There are infinitely many n such that a(n) >= 1.
Conjecture II: Natural density of numbers n such that a(n) >= 1 is 1.
Conjecture III: Numbers n such that a(n) = 0 is a finite sequence.
Conjecture IV: a(n) >= 1 for all n.
See Links section for some solutions.

			a(4) = 2 because 4! = 0 + 4 + 20 = 4 + 10 + 10.
a(24) = 2 because 24! = f(11393630) + f(118661018) + f(127041924) = f(81298034) + f(61098204) + f(143537134) where f = A000292.

Altug Alkan, A note on sequence

Cf. A000142, A000292, A102796, A104246, A102799, A267414, A308852, A341794.

Table[Length[Solve[{i*(i + 1)*(i + 2) + j*(j + 1)*(j + 2) + k*(k + 1)*(k + 2) == 6*n!, i >= 0, j >= 0, k >= 0, i <= j, j <= k, k < (6*n!)^(1/3)}, Integers]], {n, 1, 10}] (* Vaclav Kotesovec, Apr 19 2021 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula