Dieter Rautenbach ; Friedrich Regen - Graphs with many vertex-disjoint cycles

dmtcs:587 - Discrete Mathematics & Theoretical Computer Science, September 9, 2012, Vol. 14 no. 2 -
Graphs with many vertex-disjoint cycles

Authors: Dieter Rautenbach 1; Friedrich Regen 1

  • 1 Institut für Optimierung und Operations Research

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 is an element of 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 P(k). As an algorithmic consequence we describe algorithms calculating minmu(G)-nu(G), k + 1 in linear time for fixed k.

Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: September 9, 2012
Accepted on: June 9, 2015
Submitted on: August 11, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 229 times.
This article's PDF has been downloaded 277 times.