Packing edge-disjoint cycles in graphs and the cyclomatic number

Harant, Jochen GND; Rautenbach, Dieter GND; Regen, Friedrich GND; Recht, Peter

For a graph G let \mu (G) denote the cyclomatic number and let \nu (G) denote the maximum number of edge-disjoint cycles of G. We prove that for every k \geq 0 there is a nite set P(k) such that every 2-connected graph G for which \mu (G) - \nu (G) = k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k \leq 2 exactly.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved