Partitioning series-parallel multigraphs into υ*-excluding edge covers  

Partitioning series-parallel multigraphs intoν*-excluding edge covers

作　　者：LIU Guizhen, DENG Xiaotie & XU Changqing School of Mathematics and System Science, Shandong University, Jinan 250100, China Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China Department of Applied Mathematics, Hebei University of Technology, Tianjin 300130, China 

出　　处：《Science China Mathematics》2006年第8期1082-1093,共12页中国科学：数学（英文版）

基　　金：This work was partially supported by the National Natural Science Foundation of China(Grant No.10471078);the Special Research Foundation for the Doctoral Program of Higher Education of China(Grant No.20040422004);Hong Kong Research Grants Council(Grant No.CityU 1056/01E).

摘　　要：We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(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 k′(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.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.

关 键 词：SERIES-PARALLEL graph  edge-connectivity  EDGE cover coloring  MIN-MAX theorem. 

分 类 号：O157.5[理学—数学]