|
|||||
|
|
| 系列平行图的除V*外的边覆盖划分 | |
| 作者姓名： | 刘桂真 邓小铁 徐常青 |
| 作者单位： | (1)山东大学数学与系统科学学院 ,济南 250100 ,中国;(2)香港城市大学计算机系 ,香港 ,中国;(3)河北工业大学应用数学系 ,天津 300130 ,中国 |
| 基金项目： | 国家自然科学基金(批准号：10471078)，高校博士点基金(批准号：20040422004)，香港研究基金(批准号：CityU 1056/01E)资助项目 |
| 摘 要： | 任意给定系列平行图G的一个顶点v*, 则G的边集可划分为k=min {κ′(G)+1, δ(G)}个子集, 使得每一个边子集覆盖可能除v*以外的所有顶点, 其中δ(G)为G的最小度, κ′(G)为G的边连通度. 另外, 证明了该结果是最好的可能, 并且通过此证明过程得到一个可找到该划分的多项式时间算法. |
| 关 键 词： | 边连通度 边覆盖染色 极大-极小定理 系列平行图 |
| 收稿时间： | 2005-09-03 |
| 修稿时间： | 2005-09-03 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 | |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 | |