Journal of Combinatorics

Volume 4 (2013)

Number 4

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

Pages: 457 – 468

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n4.a5

Authors

Jonas Hägglund (Department of Mathematics and Mathematical Statistics, Umeå University, Sweden)

Klas Markström (Department of Mathematics and Mathematical Statistics, Umeå University, Sweden)

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.

Full Text (PDF format)