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