- 相關推薦
Partitioning series-parallel multigraphs into υ*-excluding edge covers
We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for υ*, where δ(G) is the minimum degree of G and κ'(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.
作 者： LIU Guizhen DENG Xiaotie XU Changqing 作者單位： LIU Guizhen(School of Mathematics and System Science, Shandong University, Jinan 250100, China)DENG Xiaotie(Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China)
XU Changqing(Department of Applied Mathematics, Hebei University of Technology, Tianjin 300130, China)
刊 名： 中國科學A輯（英文版） SCI 英文刊名： SCIENCE IN CHINA (MATHEMATICS) 年，卷(期)： 2006 49(8) 分類號： O1 關鍵詞： series-parallel graph edge-connectivity edge cover coloring min-max theorem【Partitioning series-parallel multigr】相關文章：