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

DOI10.4310/JOC.2013.V4.N4.A5MaRDI QIDQ2449975zbMATH OpenFDO

Authors Jonas Hägglund, Klas Markström

Publication date 13 May 2014

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3088

zbMATH Keywords

cycle covercycle double covering

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper we show that many snarks have shortest cycle covers of length $frac43m+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 $frac43m+o(m)$. In particular we prove that graphs with perfect matching index at most 4 have cycle covers of length $frac43m$ and satisfy the $(1,2)$-covering conjecture of Zhang, and that graphs with large circumference have cycle covers of length close to $frac43m$. We also prove some results for graphs with low oddness and discuss the connection with Jaeger's Petersen colouring conjecture.

Recommendations

• Short cycle covers of graphs with minimum degree three
• Short cycle covers and the cycle double cover conjecture
• scientific article; zbMATH DE number 1151805
• Cubic graphs with no short cycle covers

Cited in

(3)

• scientific article; zbMATH DE number 4061294 (Why is no real title available?)
• Cubic graphs with no short cycle covers
• Short cycle covers and the cycle double cover conjecture

This page was built for publication: Shortest cycle covers and cycle double covers with large 2-regular subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2449975)