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.