A370001 -id:A370001 - cp's OEIS frontend

A263342 Irregular triangle read by rows: T(n,k) is the number of unlabeled graphs with n vertices containing exactly k non-isomorphic induced subgraphs, 1 <= n <= k < A370001(n).

1, 2, 2, 2, 2, 2, 5, 2, 2, 0, 1, 8, 4, 10, 7, 2, 2, 0, 0, 4, 4, 6, 6, 14, 16, 14, 22, 16, 20, 16, 10, 4, 2, 2, 0, 0, 0, 0, 4, 4, 4, 10, 8, 8, 16, 10, 20, 32, 42, 36, 40, 48, 74, 56, 68, 76, 60, 74, 72, 60, 72, 64, 26, 34, 14, 8, 2

Offset: 1

Christian Stump, Oct 15 2015

Row sums give A000088, n >= 1.

There are at most A000171(n) odd terms in the n-th row, because complementary graphs have the same number of induced subgraphs. - Pontus von Brömssen, Mar 09 2024

			Triangle begins:
  1;
  2;
  2,2;
  2,2,5,2;
  2,0,1,8,4,10,7,2;
  2,0,0,4,4,6,6,14,16,14,22,16,20,16,10,4,2;
  ...

Pontus von Brömssen, Table of n, a(n) for n = 1..279 (rows n = 1..9)
FindStat - Combinatorial Statistic Finder, The number of induced subgraphs.

Cf. A000088, A000171, A370001.

T(n,n) = 2 for n >= 2, because the empty graph and the complete graph are the only n-vertex graphs having only n non-isomorphic induced subgraphs. - Pontus von Brömssen, Mar 09 2024

a(34) and beyond from Pontus von Brömssen, Mar 09 2024

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

Original entry on oeis.org

1, 2, 3, 5, 8, 16, 31, 62, 129

Offset: 1

Pontus von Brömssen, Feb 08 2024

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.)

			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.

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.

Cf. A001349, A308852, A370001 (not necessarily connected subgraphs), A370003.

a(n) <= Sum_{k=1..n} min(A001349(k),binomial(n,k)).

cp's OEIS Frontend

A263342 Irregular triangle read by rows: T(n,k) is the number of unlabeled graphs with n vertices containing exactly k non-isomorphic induced subgraphs, 1 <= n <= k < A370001(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions