A352214 Largest number of maximal claw-free node-induced subgraphs of an n-node graph.

1, 1, 1, 4, 7, 11, 23, 44, 71

Offset

1,4

Comments

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

Links

Table of n, a(n) for n=1..9.

Formula

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 71^(1/9) = 1.60581... .

Example

All graphs with at most three nodes are claw-free, so a(n) = 1 for n <= 3 and any graph is optimal.
For 4 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal claw-free subgraphs:
  n = 4: K_{1,3};
  n = 5: K_{1,4};
  n = 6: K_{1,5}, K_{3,3} with one edge removed, and K_{3,3};
  n = 7: K_{3,4} with one edge removed;
  n = 8: K_{4,4} with one edge removed;
  n = 9: K_{4,5} with one edge removed.

Crossrefs

Cf. A022562, A086991.

For a list of related sequences, see cross-references in A342211.

Sequence in context: A074705 A352216 A288111 * A179165 A369546 A128836

Adjacent sequences: A352211 A352212 A352213 * A352215 A352216 A352217

Keyword

nonn,more

Author

Pontus von Brömssen, Mar 08 2022

Status

approved