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

作　　者：刘桂真[1] 邓小铁[2] 徐常青[3] 

机构地区：[1]山东大学数学与系统科学学院,济南250100 [2]香港城市大学计算机系 [3]河北工业大学应用数学系,天津300130

出　　处：《中国科学（A辑）》2006年第6期659-668,共10页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10471078);高校博士点基金(批准号:20040422004);香港研究基金(批准号:CityU 1056/01E)资助项目

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

关 键 词：系列平行图 边连通度 边覆盖染色 极大-极小定理 

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