login
A370002
Maximum number of connected induced subgraphs, up to isomorphism, of an n-vertex graph.
2
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
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
KEYWORD
nonn,more
AUTHOR
STATUS
approved