Skip to main content
profile image
Selected Works of Bernard Lidický
Article
Short Cycle Covers of Graphs with Minimum Degree Three
SIAM Journal on Discrete Mathematics (2010)
  • Tomáš Kaiser, University of West Bohemia
  • Bernard Lidicky, Charles University, Prague
  • Daniel Král', Charles University, Prague
  • Pavel Nejedlý, Charles University, Prague
  • Robert Šámal, Charles University, Prague
Download Find in your library
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/21 ≈ 1.619m,
and every bridgeless graph with minimum degree three has a cycle cover of total length at most
44m/27 ≈ 1.630m.



Keywords
  • cycle cover,
  • cycle double cover,
  • shortest cycle cover
Disciplines
Publication Date
2010
DOI
10.1137/080717468
Publisher Statement
Copyright 2010 Society for Industrial and Applied Mathematics.
Citation Information
Tomáš Kaiser, Bernard Lidicky, Daniel Král', Pavel Nejedlý, et al.. "Short Cycle Covers of Graphs with Minimum Degree Three" SIAM Journal on Discrete Mathematics Vol. 24 Iss. 1 (2010) p. 330 - 355
Available at: http://works.bepress.com/bernard-lidicky/3/
Creative Commons license
Creative Commons License
This work is licensed under a Creative Commons CC_BY-NC International License.