Conjecture on extremal graphs for linearly long induced cycles
Let , let , and let be the maximum number of induced cycles of length in a graph on vertices. Let be the set of graphs attaining this maximum, and call a graph a cyclic braid of length as in the paper. The linear-length induced-cycle conjecture. If , then for sufficiently large the only graphs in are cyclic braids of length . 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
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.