Short cycle covers of cubic graphs and intersecting 5-circuits

01/30/2019

∙

by   Robert Lukoťka, et al.

∙

0

∙

share

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 · m (≈ 1.570 m). Moreover, if the graph is cyclically 4-edge-connected we obtain a cover of length at most 47/30 · m ≈ 1.567 m.