首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号