|
|
A352669
|
|
Maximum number of induced cycles in an n-node graph.
|
|
5
|
|
|
0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 225
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 07 2022
|
|
STATUS
|
approved
|
|
|
|