Conjecture on extremal graphs for linearly long induced cycles

About 10 years old · traced to

Let c∈(0,1)c\in(0,1), let l(n)=⌈cn⌉l(n)=\lceil cn\rceil, and let c(n,l)c(n,l) be the maximum number of induced cycles of length ll in a graph on nn vertices. Let C(n,l)C(n,l) be the set of graphs attaining this maximum, and call a graph a cyclic braid of length ll as in the paper. The linear-length induced-cycle conjecture. If l(n)=⌈cn⌉l(n)=\lceil cn\rceil, then for sufficiently large nn the only graphs in C(n,l)C(n,l) are cyclic braids of length ll. The paper determines the extremal graphs for several related induced-cycle problems, but this linear-length question is presented as an expected statement and remains unresolved.

References

Primary source

Natasha Morrison and Alex Scott, “Maximising the number of induced cycles in a graph”, arXiv:1603.02960 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.