Packing edge-disjoint cycles in graphs and the cyclomatic number

Harant, Jochen GND; Rautenbach, Dieter GND; Regen, Friedrich GND; Recht, Peter

For a graph G let \mu (G) denote the cyclomatic number and let \nu (G) denote the maximum number of edge-disjoint cycles of G. We prove that for every k \geq 0 there is a nite set P(k) such that every 2-connected graph G for which \mu (G) - \nu (G) = k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k \leq 2 exactly.

Zitieren

Zitierform:

Harant, Jochen / Rautenbach, Dieter / Regen, Friedrich / et al: Packing edge-disjoint cycles in graphs and the cyclomatic number. 2008.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export