scientific article; zbMATH DE number 140148
[For the entire collection see Zbl 0747.00036.] For a loopless undirected graph \(G\) with possible multiple edges, let \(\text{cc}(G)\) \((\text{sc}(G))\) denote the minimal number of cycles necessary to cover all edges of \(G\) at least once (twice). It was recently conjectured by Bondy that for a simple 2-edge connected graph \(G\) with \(n\) vertices \(\text{sc}(G)\leq n-1\) and \(\text{cc}(G)\leq(2n- 1)/3\), where the first bound was shown to be correct for simple plane triangulations. This paper announces some results for planar triangulations and for 2-edge connected planar graphs which approximate the Bondy conjecture for \(\text{cc}(G)\). The strongest results are obtained when \(G\) has no subdivision of \(K_ 4\) and within this class a characterization is announced of the graphs where Bondy's bound on \(\text{cc}(G)\) is tight.
- Hajós' conjecture and small cycle double covers of planar graphs
- Small cycle double covers of 4-connected planar graphs
- Cycle covers of planar 2-edge-connected graphs
- Small \(\ell\)-edge-covers in \(k\)-connected graphs
- Dicycle cover of Hamiltonian oriented graphs
- Classes of line graphs with small cycle double covers
- Maximal planar graphs of diameter two
- scientific article; zbMATH DE number 1185135 (Why is no real title available?)
- scientific article; zbMATH DE number 30747 (Why is no real title available?)
- scientific article; zbMATH DE number 554189 (Why is no real title available?)
- scientific article; zbMATH DE number 1779394 (Why is no real title available?)
- Circuit double covers of graphs
- Packing and covering odd cycles in cubic plane graphs with small faces
- Small cycle covers of 3-connected cubic graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028533)
