A352669 Maximum number of induced cycles in an n-node graph.

0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 225

Offset: 1

Author

Pontus von Brömssen, Mar 26 2022

Keywords

• nonn
• hard
• more

Comments

For 3 <= n <= 11, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is the unique extremal graph, but a(12) = 225 > binomial(12,3), where the unique extremal graph is K_{6,6}.

Morrison and Scott (2017) prove that, for sufficiently large n (they say it ought to be true for n >= 30), a(n) = A276401(n), with the unique extremal graph being the empty cyclic braid graph with one cluster of size 4 if n == 1 (mod 3), one cluster of size 2 if n == 2 (mod 3), and all other clusters of size 3. (The empty cyclic braid graph is obtained by arranging clusters of nodes of the appropriate sizes in a cycle and joining all pairs of nodes in neighboring clusters with edges.) For 14 <= n <= 21, this graph is not extremal, because the balanced bipartite graph K_{floor(n/2),ceiling(n/2)} has A028723(n+1) > A276401(n) induced cycles.

Links

• Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 43e7869.
• 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, A028723, A276401.

Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352667 (paw graph), A352668 (diamond graph).

Extensions

a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 07 2022