Subgraph coverings and edge switchings (Q1850576): Difference between revisions

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.