Conjecture on extremal graphs for linearly long induced cycles
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Natasha Morrison and Alex Scott, “Maximising the number of induced cycles in a graph”, arXiv:1603.02960 (2017).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.