Skip to Main content Skip to Navigation
Journal articles

Graphs with many vertex-disjoint cycles

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:27:41 PM
Last modification on : Monday, March 4, 2019 - 1:44:09 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:41:21 PM


Files produced by the author(s)




Dieter Rautenbach, Friedrich Regen. Graphs with many vertex-disjoint cycles. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.75--82. ⟨10.46298/dmtcs.587⟩. ⟨hal-00990590⟩



Record views


Files downloads