A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

1, 1, 1, 4, 10, 20, 35, 56, 84

Offset: 1

Author

Pontus von Brömssen, Mar 08 2022

Keywords

• nonn
• more

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

In the following, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges.

a(10) >= 140 by FCB(2, 2, 2, 2, 2);

a(11) >= 268 by FCB(2, 2, 2, 2, 3);

a(12) >= 517 by FCB(2, 2, 3, 2, 3);

a(13) >= 911 by FCB(2, 3, 2, 3, 3);

a(14) >= 1515 by FCB(2, 3, 3, 3, 3);

a(15) >= 2525 by FCB(3, 3, 3, 3, 3).

Examples

			For 3 <= n <= 9, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal (it is the unique optimal graph for 4 <= n <= 9), but a(10) >= 140 > binomial(10,3).
		

Links

• Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

Crossrefs

Cf. A000292, A076315, A076322.

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

Formula

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

Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .