The author proves that the edges of a connected graph \(G\) can be covered with at most \(\lceil n/2\rceil\) paths, a result conjectured by Chung. He also proves a conjecture of Bondy which states that, if \(G\) is \(2\)-connected, then its edges can be covered by at most \(\lceil (2n-1)/3\rceil\) circuits. With the weaker assumption that \(G\) is \(2\)-edge connected he shows that there is a covering with at most \(\lceil 3(n-1)/4\rceil\) circuits. All bounds are tight.
Recommendations
Cites work
- An Erdős-Gallai conjecture
- An upper bound for the path number of a graph
- Covering the edges of a connected graph by paths
- Graph theory
- scientific article; zbMATH DE number 4214053 (Why is no real title available?)
- scientific article; zbMATH DE number 3253072 (Why is no real title available?)
- On the coverings of graphs
- The Representation of a Graph by Set Intersections
Cited in
(25)- A remark on covering graphs
- A note on covering the edges of a graph with bonds
- Small cycle cover of 2-connected cubic graphs
- Covers of Eulerian graphs
- Graphs with almost all edges in long cycles
- Path decompositions and Gallai's conjecture
- How many circuits determine an oriented matroid?
- Covering the edges of a connected graph by paths
- An overview of graph covering and partitioning
- A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
- The codiameter of a 2-connected graph
- Dicycle cover of Hamiltonian oriented graphs
- On a connection between the switching separability of a graph and that of its subgraphs
- Path and cycle decompositions of dense graphs
- Covering 2-connected 3-regular graphs with disjoint paths
- scientific article; zbMATH DE number 861353 (Why is no real title available?)
- Cycle packing
- Maximizing the number of independent sets of fixed size in Kn‐covered graphs
- The Number of Cliques in Graphs Covered by Long Cycles
- Small cycle covers of 3-connected cubic graphs
- Towards the Erdős-Gallai cycle decomposition conjecture
- Towards the Erdős-Gallai cycle decomposition conjecture
- Cycles in 2-connected graphs
- Regular bipartite decompositions of pseudorandom graphs
- Path odd-covers of graphs
This page was built for publication: Subgraph coverings and edge switchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850576)
