2019/01/30 by Lukoťka, Robert
#05C38 #05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1901.10718
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.