Short cycle covers of cubic graphs and intersecting 5-circuits

Abstract

A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph with $m$ edges has a cycle cover of length at most $212/135\cdot m(\approx 1.570m)$. Moreover, if the graph is cyclically $4$-edge-connected we obtain a cover of length at most $47/30\cdot m\approx 1.567m$.

25 pages