A370003 -id:A370003 - cp's OEIS frontend

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

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

A370301 Least number of vertices of a universal graph for cycles up to length n, i.e., a graph containing induced cycles of lengths 3..n.

Original entry on oeis.org

3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16

Offset: 3

Pontus von Brömssen, Feb 14 2024

			In the following table, graphs with a(n) vertices and induced cycles of lengths 3..n are shown. The vertices 1, 2, ..., n constitute an induced cycle; only the additional vertices n+1, ..., a(n) and their lists of neighbors are given.
   n | a(n) | vertices outside the given induced n-cycle and their neighbors
  ---+------+---------------------------------------------------------------
   3 |   3  | none
   4 |   5  | 5:1,2
   5 |   6  | 6:1,2,4
   6 |   7  | 7:1,2,4
   7 |   9  | 8:1,2,4,9; 9:6,8
   8 |  10  | 9:1,3,4,10; 10:6,9
   9 |  11  | 10:1,5,11; 11:2,5,10
  10 |  12  | 11:1,2,4,7; 12:6,9
  11 |  13  | 12:1,2,5,6,8; 13:3,11
  12 |  14  | 13:1,2,5,7; 14:3,6,8
  13 |  16  | 14:1,3,4,7,15; 15:10,14; 16:6,9
For n = 7, the graph with a cycle 1-2-...-7-1 and two additional vertices with edges 8-1, 8-2, 8-4, 8-9, and 9-6 contains induced cycles of lengths 3..7: 1-2-8-1, 2-3-4-8-2, 1-7-6-9-8-1 (for example), 1-7-6-5-4-8-1, and 1-2-3-4-5-6-7-1. No such graph with fewer vertices exists, so a(7) = 9.

Wikipedia, Universal graph.

Cf. A097911, A348638, A370003, A370302.

a(n) = A370302(2^(n-2)-1).

a(n) <= a(n-1) + 2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula