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

Abstract

In this paper we show that many snarks have shortest cycle covers 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.

References in corpus (3)

• 1-factor and cycle covers of cubic graphs
• On the perfect matching index of bridgeless cubic graphs
• On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings