SHORT CYCLE COVERS ON CUBIC GRAPHS BY CHOOSING A 2-FACTOR.

We show that every bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. Moreover, if G does not contain any intersecting circuits of length 5, then G has a cycle cover of length 212/135 ·m ≈ 1.570m, and if G contains no 5-circuits, then it has a cycle cover of length at most 14/9·m ≈ 1.556m. 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. [ABSTRACT FROM AUTHOR]