The equality conjecture for shortest cycle covers and triangle expansions

From papers

Let GG be a cubic graph. For UV(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)=43E(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.

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

No solutions have been posted yet.