The equality conjecture for shortest cycle covers and triangle expansions

Let GG be a cubic graph. For U⊆V(G)U\subseteq V(G), let GUG_U be the cubic graph obtained by expanding each vertex of UU into a triangle. For a bridgeless cubic graph GG, let T(G)T(G) be the minimum size of a set UU such that the edge-set of GUG_U can be covered with four perfect matchings. Let scc(G)scc(G) denote the length of a shortest cycle cover of GG. Equality conjecture for scc(G)scc(G) and T(G)T(G). If GG is a 33-edge-connected cubic graph, then

scc(G)=43∣E(G)∣+T(G).scc(G)=\frac{4}{3}|E(G)|+T(G).

The paper proves the corresponding inequality for bridgeless cubic graphs and proposes equality under the stronger 33-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

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.