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