### Graphs with many Vertex-Disjoint Cycles

*Dieter Rautenbach, Friedrich Regen*

#### Abstract

We study graphs G in which the maximum number of
vertex-disjoint cycles ν(G) is close to the cyclomatic
number µ(G), which is a natural upper bound for
ν(G). Our main result is the existence of a finite set
P(k) of graphs for all
k∈N

_{0}such that every 2-connected graph G with µ(G)-ν(G)=k arises by applying a simple extension rule to a graph in P(k). As an algorithmic consequence we describe algorithms calculating &min;{µ(G)-ν(G), k+1} in linear time for fixed k.Full Text: PDF PostScript