A352210 Largest number of maximal 2-degenerate node-induced subgraphs of an n-node graph.

1, 1, 1, 4, 10, 20, 35, 56, 97

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) >= 97^(1/9) = 1.66246... .

Example

For 3 <= n <= 8, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal, but a(9) = 97 > binomial(9,3) with the optimal graph being the complement of the disjoint union of K_3 and K_{3,3}. The optimal graph is unique when 4 <= n <= 9.

Crossrefs

Cf. A000292, A352067.

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

Sequence in context: A000292 A352669 A101552 * A038419 A301208 A057319

Adjacent sequences: A352207 A352208 A352209 * A352211 A352212 A352213

Keyword

nonn,more

Author

Pontus von Brömssen, Mar 08 2022

Status

approved