Shortest cycle covers and cycle double covers with large 2-regular subgraphs

In this paper, we show that many snarks have a shortest cycle cover of length $\frac{4}{3}m + c$ for a constant $c$, where $m$ is the number of edges in the graph, in agreement with the conjecture that all snarks have shortest cycle covers of length $\frac{4}{3}m + o(m)$. In particular, we prove that graphs with perfect matching index at most $4$ have cycle covers of length $\frac{4}{3}m$ and satisfy the $(1, 2)$-covering conjecture of Zhang, and that graphs with large circumference have cycle covers of length close to $\frac{4}{3}m$. We also prove some results for graphs with low oddness and discuss the connection with Jaeger’s Petersen colouring conjecture.

Keywords

cycle cover, cycle double covering

2010 Mathematics Subject Classification

Primary 05C70. Secondary 05C38.

Full Text (PDF format)

Published 27 December 2013