Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits

DOI10.1137/19M1241866MaRDI QIDQ5210904zbMATH OpenOpenAlexWikidataFDO

Authors R. Lukot'ka

Publication date 16 January 2020

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

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

zbMATH Keywords

cubic graphcycle covershort cycle cover

Mathematics Subject Classification ID

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

Abstract: A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph with $m$ edges has a cycle cover of length at most $212/135cdotm(approx1.570m)$. Moreover, if the graph is cyclically $4$-edge-connected we obtain a cover of length at most $47/30cdotmapprox1.567m$.

Recommendations

• Short cycle covers of cubic graphs
• Five cycle double covers of some cubic graphs
• A note on shortest cycle covers of cubic graphs
• Shortest circuit covers of cubic graphs
• Short cycle covers on cubic graphs by choosing a 2-factor
• scientific article; zbMATH DE number 57416
• Cubic graphs with no short cycle covers
• Shortest coverings of graphs with cycles
• Cycle covers of cubic multigraphs
• Cyclically five-connected cubic graphs

Cites work

• Covering Multigraphs by Simple Circuits
• Flows and generalized coloring theorems in graphs
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Integer 4-flows and cycle covers
• Maximum matching and a polyhedron with 0,1-vertices
• Polyhedral decompositions of cubic graphs
• Short cycle covers and the cycle double cover conjecture
• Short cycle covers of graphs with minimum degree three
• Short cycle covers on cubic graphs by choosing a 2-factor
• Shortest coverings of graphs with cycles
• Small snarks with large oddness

Cited in

(14)

• Short circuit covers for regular matroids with a nowhere zero 5-flow
• Shortest circuit covers of cubic graphs
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• 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 with minimum degree three
• Cycles Intersecting Edge-Cuts of Prescribed Sizes
• Cycles intersecting edge-cuts of prescribed sizes
• 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
• Avoiding 5-Circuits in 2-Factors of Cubic Graphs
• A note on Alon-Tarsi shortest cycle cover conjecture

This page was built for publication: Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits

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