Short cycle covers of graphs with minimum degree three

DOI10.1137/080717468MaRDI QIDQ3084229zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tomáš Kaiser, Bernard Lidický, Pavel Nejedlý, Robert Šámal, Daniel Král'

Publication date 15 March 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cycle covercycle double covershortest cycle cover

Mathematics Subject Classification ID

Flows in graphs (05C21) Paths and cycles (05C38)

Abstract: The Shortest Cycle Cover Conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with $m$ edges can be covered by cycles of total length at most $7m/5=1.400m$. We show that every cubic bridgeless graph has a cycle cover of total length at most $34m/21approx1.619m$ and every bridgeless graph with minimum degree three has a cycle cover of total length at most $44m/27approx1.630m$.

Recommendations

• Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits
• Cubic graphs with no short cycle covers
• Short cycle covers of cubic graphs
• Short cycle covers of graphs with at most 77\% vertices of degree two
• A note on shortest cycle covers of cubic graphs

Cited in

(25)

• Cycle covering in bridgeless graphs
• Short signed circuit covers of signed graphs
• Integer 4-flows and cycle covers
• Note on integer 4-flows in graphs
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• Short cycle covers of graphs with at most 77\% vertices of degree two
• Shortest cycle covers and cycle double covers with large 2-regular subgraphs
• A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface
• Short cycle covers on cubic graphs by choosing a 2-factor
• A note on shortest cycle covers of cubic graphs
• Short cycle covers of graphs and nowhere-zero flows
• Covering Graphs by Cycles
• Short cycle covers of cubic graphs
• scientific article; zbMATH DE number 219252 (Why is no real title available?)
• 1-factor and cycle covers of cubic graphs
• Cubic graphs with no short cycle covers
• Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits
• Low congestion cycle covers and their applications
• Small cycle covers of 3-connected cubic graphs
• Some snarks are worse than others
• Five-cycle double cover and shortest cycle cover
• On Fan's conjecture about 4-flow
• Signed cycle double covers
• Postman tours and cycle covers
• A note on Alon-Tarsi shortest cycle cover conjecture

This page was built for publication: Short cycle covers of graphs with minimum degree three

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