A342213 Largest number of maximal planar node-induced subgraphs of an n-node graph.

1, 1, 1, 1, 5, 15, 35, 70, 126, 211

Offset

1,5

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). - Pontus von Brömssen, Mar 03 2022

a(11) >= 381, because the complete 5-partite graph K_{1,1,3,3,3} has 381 maximal planar subgraphs.

Links

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

Formula

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

Lim_{n->oo} a(n)^(1/n) >= 381^(1/11) = 1.71644... .

Example

For 4 <= n <= 9, a(n) = binomial(n,4) = A000332(n) and the complete graph is optimal, but a(10) = 211 > 210 = binomial(10,4) with the optimal graph being the complete 6-partite graph K_{1,1,1,1,3,3}. The optimal graph is unique when 5 <= n <= 10.

Crossrefs

Cf. A000332, A003094, A005470.

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

Sequence in context: A341184 A090580 A000332 * A140227 A264925 A049016

Adjacent sequences: A342210 A342211 A342212 * A342214 A342215 A342216

Keyword

nonn,more

Author

Pontus von Brömssen, Mar 05 2021

Status

approved