No label defined (Q4028533)

[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.