The equality conjecture for shortest cycle covers and triangle expansions
The equality conjecture for shortest cycle covers and triangle expansions
Let be a cubic graph. For , let be the cubic graph obtained by expanding each vertex of into a triangle. For a bridgeless cubic graph , let be the minimum size of a set such that the edge-set of can be covered with four perfect matchings. Let denote the length of a shortest cycle cover of . Equality conjecture for and . If is a -edge-connected cubic graph, then
The paper proves the corresponding inequality for bridgeless cubic graphs and proposes equality under the stronger -edge-connectivity assumption. The conjecture remains open.
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
Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.