A min-max relation on packing feedback vertex sets

• 成果类型: Article
• 署名作者: Chen, Xujin; Ding, Guoli; Hu, Xiaodong; Zang, Wenan
• 署名单位: Chinese Academy of Sciences; Louisiana State University System; Louisiana State University; University of Hong Kong
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0200
• 发表日期: 2006
• 页码: 777-788
• 关键词: graphs; cycles

摘要

Let G be a graph with a nonnegative integral function w defined on V(G). A collection T of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of 3 from G leaves a forest, and every vertex v is an element of V(G) is contained in at most w(v) members of F. The weight of a cycle C in G is the sum of w(v), over all vertices v of C. The purpose of this paper is to characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle.