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  關(guān)鍵詞： series-parallel graph   edge-connectivity   edge cover coloring   min-max theorem  

【Partitioning series-parallel multigr】相關(guān)文章：

How Does the Partitioning of Evapotranspiration and Runoff between Different Processes Affect the Variability and Predic04-27