Short cycle covers of graphs with at most 77\% vertices of degree two (Q2213807)

Summary: Let \(G\) be a bridgeless multigraph with \(m\) edges and \(n_2\) vertices of degree two and let \(\operatorname{cc}(G)\) be the length of its shortest cycle cover. It is known that if \(\operatorname{cc}(G) < 1.4m\) in bridgeless graphs with \(n_2 \leqslant m/10\), then the cycle double cover conjecture holds. \textit{G. Fan} [Combinatorica 37, No. 6, 1097--1112 (2017; Zbl 1399.05180)] proved that if \(n_2 = 0\), then \(\operatorname{cc}(G) < 1.6258m\) and \(\operatorname{cc}(G) < 1.6148m\) provided that \(G\) is loopless; morever, if \(n_2 \leqslant m/30\), then \(\operatorname{cc}(G) < 1.6467m\). We show that for a bridgeless multigraph with \(m\) edges and \(n_2\) vertices of degree two, \(\operatorname{cc}(G) < 1.6148m + 0.0741n_2\). Therefore, if \(n_2=0\), then \(\operatorname{cc}(G) < 1.6148m\) even if \(G\) has loops; if \(n_2 \leqslant m/30\), then \(\operatorname{cc}(G) < 1.6173m\); and if \(n_2 \leqslant m/10\), then \(\operatorname{cc}(G) < 1.6223|E(G)|\). Our improvement is obtained by randomizing Fan's construction.