A note about shortest cycle covers
From MaRDI portal
Publication:2581631
The authors prove the following result: Let \(G\) be a graph with odd edge-connectivity \(r\). If \(r>3\), then \(G\) has a 3-cycle \((1,2)\)-cover of total length at most \((r+1)| E(G)|/r\).
Recommendations
- Shortest coverings of graphs with cycles
- A note on shortest cycle covers of cubic graphs
- Short cycle covers and the cycle double cover conjecture
- On shortest cocycle covers of graphs
- A note on short cycles in a hypercube
- A note on short cycles in digraphs
- A note on cycle lengths in graphs
- On Approximating Restricted Cycle Covers
- Approximation and Online Algorithms
Cites work
- A Contribution to the Theory of Chromatic Polynomials
- Circular flows of nearly Eulerian graphs and vertex-splitting
- Covering Multigraphs by Simple Circuits
- Cycle covering in bridgeless graphs
- Cycle covers of graphs with a nowhere-zero 4-flow
- Flows and generalized coloring theorems in graphs
- Fulkerson's conjecture and circuit covers
- Graph theory
- Graphs with the Circuit Cover Property
- scientific article; zbMATH DE number 3728302 (Why is no real title available?)
- scientific article; zbMATH DE number 3600081 (Why is no real title available?)
- scientific article; zbMATH DE number 1025912 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- Integer flows and cycle covers
- Maximum matching and a polyhedron with 0,1-vertices
- Minimum cycle coverings and integer flows
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
- On the Complexity of Finding a Minimum Cycle Cover of a Graph
- On the Imbedding of Linear Graphs in Surfaces
- Polyhedral decompositions of cubic graphs
- Proofs of two minimum circuit cover conjectures
- Short circuit covers for regular matroids with a nowhere zero 5-flow
- Short cycle covers and the cycle double cover conjecture
- Shortest Circuit Covers and Postman Tours in Graphs with a Nowhere Zero 4
- Shortest coverings of graphs with cycles
- Smallest (1, 2)‐eulerian weight and shortest cycle covering
- Tutte's 3-flow conjecture and short cycle covers
Cited in
(7)- On shortest cocycle covers of graphs
- Short cycle covers and the cycle double cover conjecture
- Covering odd cycles
- A sufficient condition for all short cycles
- Short cycle covers of graphs and nowhere-zero flows
- Parity Subgraph, Shortest Cycle Cover, and Postman Tour
- Covering the edges of a graph by three odd subgraphs
This page was built for publication: A note about shortest cycle covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581631)
