A352669 - OEIS

%I #22 Oct 13 2022 10:58:26

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

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

%C 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}.

%C 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.

%H Falk Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version 43e7869.

%H Natasha Morrison and Alex Scott, <a href="http://dx.doi.org/10.1016/j.jctb.2017.03.007">Maximising the number of induced cycles in a graph</a>, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

%Y Cf. A000292, A028723, A276401.

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

%K nonn,hard,more

%O 1,4

%A _Pontus von Brömssen_, Mar 26 2022

%E a(10)-a(12) added using tinygraph by _Falk Hüffner_, Apr 07 2022