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

Let n4n\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 n4n\geq 4, the balanced complete bipartite graph

Kn/2,n/2K_{\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.

Sources & referencesView supporting material

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.