Short cycle covers of graphs with at most 77\% vertices of degree two (Q2213807)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Short cycle covers of graphs with at most 77\% vertices of degree two |
scientific article |
Statements
Short cycle covers of graphs with at most 77\% vertices of degree two (English)
0 references
3 December 2020
0 references
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.
0 references
cycle double cover conjecture
0 references
Fan's construction
0 references