系列平行图的除V*外的边覆盖划分

作者：刘桂真; 邓小铁; 徐常青

来源：中国科学A辑:数学 , 2006, (06): 659-668.

• 系列平行图
• 边连通度
• 边覆盖染色
• 极大-极小定理

任意给定系列平行图G的一个顶点v~*,则G的边集可划分为k=min {K′(G)+1,δ(G)}个子集,使得每一个边子集覆盖可能除发~*以外的所有顶点,其中δ(G)为G的最小度,K′(G)为G的边连通度．另外,证明了该结果是最好的可能,并且通过此证明过程得到一个可找到该划分的多项式时间算法．

• 单位
  香港城市大学; 山东大学; 河北工业大学