Graphs with many vertex-disjoint cycles - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2012

Graphs with many vertex-disjoint cycles

Résumé

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.
Fichier principal
Vignette du fichier
2019-7388-1-PB.pdf (260.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990590 , version 1 (13-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
68 Consultations
1327 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More