Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

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