Durocher–Gunderson–Li–Skala conjecture on cycles in triangle-free graphs

About 11 years old · traced to

Let n≥4n\geq 4. A triangle-free graph is a graph containing no triangle, and Ka,bK_{a,b} denotes the complete bipartite graph with parts of sizes aa and bb. Durocher–Gunderson–Li–Skala conjecture. For each n≥4n\geq 4, the balanced complete bipartite graph

K⌈n/2⌉,⌊n/2⌋K_{\lceil n/2\rceil, \lfloor n/2 \rfloor}

contains more cycles than any other nn-vertex triangle-free graph. This conjecture asks for the extremal triangle-free graph maximizing the total number of cycles and arose from questions connected with path-finding algorithms. Its status is not resolved in the supplied source.

References

Primary source

Andrii Arman, David S. Gunderson and Sergei Tsaturian, “Triangle-free graphs with the maximum number of cycles”, arXiv:1501.01088 (2015).

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.