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.
References
Primary source
Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).
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
No solutions have been posted yet.