A370001 Maximum number of induced subgraphs, up to isomorphism, of an n-vertex graph.
2, 3, 5, 8, 13, 23, 41, 77, 152
Offset: 1
Examples
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.
n a(n) optimal graphs
------------------------------------
1 2 K_1 (self-complementary)
2 3 K_2
3 5 P_3 (path)
4 8 paw graph
5 13 dart graph
6 23 initial part of the Rado graph using BIT predicate (House of Graphs id 25152)
7 41 "FCZJw"
8 77 "GCrbU{" (House of Graphs id 36157), "G?qjvS"
9 152 "HPobRJm"
10 >=312 "InLEipZiG" (upper bound: 385)
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.
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, Paw Graph.
- Wikipedia, Rado graph.
Formula
a(n) <= Sum_{k=0..n} min(A000088(k),binomial(n,k)).
Comments