Contents Online
Journal of Combinatorics
Volume 4 (2013)
Number 4
Shortest cycle covers and cycle double covers with large 2-regular subgraphs
Pages: 457 – 468
DOI: https://dx.doi.org/10.4310/JOC.2013.v4.n4.a5
Authors
Abstract
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.
Published 27 December 2013