2015/09/24 by Candráková, Barbora, Lukoťka, Robert
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1509.07430
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 ⋅ m ≈ 1.570 m and if G contains no 5-circuits, then it has a cycle cover of length at most 14/9 ⋅ m ≈ 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) only depends 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.