Short Cycle Covers on Cubic Graphs by Choosing a 2-Factor
Barbora Candráková, Robert Lukoťka · SIAM Journal on Discrete Mathematics · 2016
We show that every bridgeless cubic graph $G$ with $m$ edges has a cycle cover of length at most 1.6 m. Moreover, if $G$ does not contain any intersecting circuits of length 5, then $G$ has a cycle cover of length $212/135 \cdot m \approx 1.570 m$, and if $G$ contains no 5-circuits, then it has a cycle cover of length at most $14/9 \cdot m \approx 1.556 m$. To prove our results, we show that each 2-edge-connected cubic graph $G$ on $n$ vertices has a 2-factor containing at most $n/10+f(G)$ circuits of length 5, where the value of $f(G)$ depends only on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each 3-edge-connected cubic graph on $n$ vertices has a 2-factor containing at most n/9 circuits of length 5, and each 4-edge-connected cubic graph on $n$ vertices has a 2-factor containing at most n/10 circuits of length 5.