This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A370002 #15 Mar 07 2024 08:45:48
%S A370002 1,2,3,5,8,16,31,62,129
%N A370002 Maximum number of connected induced subgraphs, up to isomorphism, of an n-vertex graph.
%C A370002 The null subgraph is not considered to be connected.
%C A370002 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.)
%H A370002 House of Graphs, <a href="https://houseofgraphs.org/graphs/25152">Graph 25152</a>.
%H A370002 House of Graphs, <a href="https://houseofgraphs.org/graphs/36157">Graph 36157</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DartGraph.html">Dart Graph</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DiamondGraph.html">Diamond Graph</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FanGraph.html">Fan Graph</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HouseGraph.html">House Graph</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KiteGraph.html">Kite Graph</a>.
%H A370002 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PawGraph.html">Paw Graph</a>.
%H A370002 Wikipedia, <a href="https://en.wikipedia.org/wiki/Rado_graph#Binary_numbers">Rado graph</a>.
%F A370002 a(n) <= Sum_{k=1..n} min(A001349(k),binomial(n,k)).
%e A370002 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.
%e A370002 .
%e A370002 n a(n) optimal graphs
%e A370002 ------------------------------
%e A370002 1 1 K_1
%e A370002 2 2 K_2
%e A370002 3 3 K_3, P_3 (path)
%e A370002 4 5 paw graph, diamond graph (K_{1,1,2})
%e A370002 5 8 dart graph, kite graph, house graph, house X-graph,
%e A370002 fan graph F_{1,4}, complement of P_2 + P_3
%e A370002 6 16 complement of the initial part of the Rado graph using
%e A370002 BIT predicate (the complement has House of Graphs id 25152),
%e A370002 "EEno"
%e A370002 7 31 "FCvdw", "FCvfw", "FCz^g", "FEjvw"
%e A370002 8 62 "GCZmp{", "GCrbU{" (House of Graphs id 36157)
%e A370002 9 129 "HCpfbmn"
%e A370002 10 >= 276 "INnAnDRUG" (upper bound: 319)
%e A370002 11 >= 595 "JonellBani_" (upper bound: 705)
%e A370002 12 >= 1304 "KonellBanibD" (upper bound: 1729)
%e A370002 .
%e A370002 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.
%Y A370002 Cf. A001349, A308852, A370001 (not necessarily connected subgraphs), A370003.
%K A370002 nonn,more
%O A370002 1,2
%A A370002 _Pontus von Brömssen_, Feb 08 2024