Let $G$ be a bridgeless multigraph with $m$ edges and $n_2$ vertices of degree two and let $cc(G)$ be the length of its shortest cycle cover. It is known that if $cc(G) < 1.4m$ in bridgeless graphs with $n_2 \le m/10$, then the Cycle Double Cover Conjecture holds. Fan (2017) proved that if $n_2 = 0$, then $cc(G) < 1.6258m$ and $cc(G) < 1.6148m$ provided that $G$ is loopless; morever, if $n_2 \le m/30$, then $cc(G) < 1.6467m$. We show that for a bridgeless multigraph with $m$ edges and $n_2$ vertices of degree two, $cc(G) < 1.6148m + 0.0741n_2$. Therefore, if $n_2=0$, then $cc(G) < 1.6148m$ even if $G$ has loops; if $n_2 \le m/30$, then $cc(G) < 1.6173m$; and if $n_2 \le m/10$, then $cc(G) < 1.6223|E(G)|$. Our improvement is obtained by randomizing Fan's construction.
@article{10_37236_9284,
author = {Anna Kompi\v{s}ov\'a and Robert Lukot'ka},
title = {Short cycle covers of graphs with at most 77\% vertices of degree two},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9284},
zbl = {1453.05053},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9284/}
}
TY - JOUR
AU - Anna Kompišová
AU - Robert Lukot'ka
TI - Short cycle covers of graphs with at most 77\% vertices of degree two
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9284/
DO - 10.37236/9284
ID - 10_37236_9284
ER -
%0 Journal Article
%A Anna Kompišová
%A Robert Lukot'ka
%T Short cycle covers of graphs with at most 77\% vertices of degree two
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9284/
%R 10.37236/9284
%F 10_37236_9284
Anna Kompišová; Robert Lukot'ka. Short cycle covers of graphs with at most 77\% vertices of degree two. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9284
