cp's OEIS Frontend

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

%I A370001 #14 Mar 10 2024 00:20:27
%S A370001 2,3,5,8,13,23,41,77,152
%N A370001 Maximum number of induced subgraphs, up to isomorphism, of an n-vertex graph.
%C A370001 The null subgraph is included in the counts.
%C A370001 A graph and its complement have the same number of induced subgraphs.
%C A370001 The number of terms in the n-th row of A263342 is a(n)-n.
%H A370001 House of Graphs, <a href="https://houseofgraphs.org/graphs/25152">Graph 25152</a>.
%H A370001 House of Graphs, <a href="https://houseofgraphs.org/graphs/36157">Graph 36157</a>.
%H A370001 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DartGraph.html">Dart Graph</a>.
%H A370001 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PawGraph.html">Paw Graph</a>.
%H A370001 Wikipedia, <a href="https://en.wikipedia.org/wiki/Rado_graph#Binary_numbers">Rado graph</a>.
%F A370001 a(n) <= Sum_{k=0..n} min(A000088(k),binomial(n,k)).
%e A370001 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. Only one graph in each complementary pair is listed. If there is no known simple description or name of the optimal graphs, they are shown in the graph6 format.
%e A370001    n   a(n)   optimal graphs
%e A370001   ------------------------------------
%e A370001    1     2    K_1 (self-complementary)
%e A370001    2     3    K_2
%e A370001    3     5    P_3 (path)
%e A370001    4     8    paw graph
%e A370001    5    13    dart graph
%e A370001    6    23    initial part of the Rado graph using BIT predicate (House of Graphs id 25152)
%e A370001    7    41    "FCZJw"
%e A370001    8    77    "GCrbU{" (House of Graphs id 36157), "G?qjvS"
%e A370001    9   152    "HPobRJm"
%e A370001   10 >=312    "InLEipZiG" (upper bound: 385)
%e A370001 For n = 3, the path graph has 5 induced subgraphs: the null graph, K_1, K_2, the empty graph on 2 vertices, and itself. This is the maximum possible, so a(3) = 5.
%Y A370001 Cf. A000088, A097911, A263342, A370002 (connected subgraphs).
%K A370001 nonn,more
%O A370001 1,1
%A A370001 _Pontus von Brömssen_, Feb 08 2024