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∈N0 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