Graphs with many vertex-disjoint cycles

We study graphs G in which the maximum number of vertex-disjoint cycles \nu(G) is close to the cyclomatic number \mu(G) which is a natural upper bound for \nu(G). Our main result is the existence of a finite set P(k) of graphs for all k \in \mathbb{N}_0 such that every 2-connected graph G with \mu(G) \nu (G) = k arises by applying a simple extension rule to a graph in \mathcal{P}(k). As an algorithmic consequence we describe algorithms calculating min{\mu(G)-\nu(G); k + 1} in linear time for fixed k.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved