Packing edge-disjoint cycles in graphs and the cyclomatic number |
| |
Authors: | Jochen Harant Peter Recht |
| |
Affiliation: | a Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany b Lehrstuhl für Operations Research und Wirtschaftsinformatik, Universität Dortmund, D-44227 Dortmund, Germany |
| |
Abstract: | For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly. |
| |
Keywords: | Graph Cycle Packing Cyclomatic number |
本文献已被 ScienceDirect 等数据库收录! |