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