Zhang's depth-two shortest cycle cover conjecture

A cycle cover of a graph is a collection of cycles covering every edge. The depth of an edge in a cycle cover is the number of cycles containing it, and the depth of the cover is the maximum edge depth. A shortest cycle cover is one of minimum total length. Zhang's depth-two conjecture. Every 33-edge-connected graph GG admits a shortest cycle cover of depth 22.

This conjecture would imply the equality conjecture relating scc(G)scc(G) and T(G)T(G) in the paper. It remains open.

Sources & referencesView supporting material

Primary source

Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).

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.