Durocher–Gunderson–Li–Skala conjecture on cycles in triangle-free graphs
Durocher–Gunderson–Li–Skala conjecture on cycles in triangle-free graphs
Let . A triangle-free graph is a graph containing no triangle, and denotes the complete bipartite graph with parts of sizes and . Durocher–Gunderson–Li–Skala conjecture. For each , the balanced complete bipartite graph
contains more cycles than any other -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.