| 将小直径图划分为导出匹配 |
| |
| 引用本文： | 杨爱峰,原晋江.将小直径图划分为导出匹配[J].高校应用数学学报(英文版),2004,19(3):245-251. |
| |
| 作者姓名： | 杨爱峰 原晋江 |
| |
| 作者单位： | [2]Dept.ofAppl.Math.,SouthChinaUniv.ofTech.,Guangdong510640,China. [3]Dept.ofMath.,ZhengzhouUniv.,Henan450052,China. |
| |
| 摘 要： | Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V1,V2,…Vk)of V(G) such that for each i(1≤i≤k),GVi] is 1 regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP- complete;induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.
|
| 关 键 词： | 小直径图 导出匹配 正整数 划分 |
PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
