直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性(英文)  

2-Induced-Matching Partition Problem and 2-Induced-Matching Cover Problem of Graphs with Diameter 5 are NP-complete

作　　者：禹继国[1] 郑永猛[1] 刘桂真[2] 张永红[1] 

机构地区：[1]曲阜师范大学计算机科学学院,日照276826 [2]山东大学数学与系统科学学院,济南250100

出　　处：《运筹学学报》2009年第2期41-47,共7页Operations Research Transactions

基　　金：supported by NNSF(10471078) of China;RFDP(20040422004) of Higher Education;Promotional Foundation(2005BS01016) for Excellent Middle-aged or Young Scientists of Shandong Province;UF(XJ0609) and DRF of QFNU

摘　　要：给定一个简单图G和正整数k,具有完美匹配的图G的k-导出匹配划分是对顶点集V(G)的一个k-划分(V_1,V_2,…,V_k),其中对每一个i(1≤i≤k),由V_i导出的G的子图G[V_i]是1-正则的.k-导出匹配划分问题是指对给定的图G,判定G是否存在一个k-导出匹配划分.令M_1,M_2,…,M_k为图G的k个导出匹配,如果V(M_1)∪V(M_2)∪…∪V(M_k)=V(G),则我们称{M_1,M_2…,M_k}是G的k-导出匹配覆盖. k-导出匹配覆盖问题是指对给定的图G,判定G是否存在k-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2-划分问题和导出匹配2-覆盖问题都是NP-完全的.Given a simple graph G and a positive integer k, a k-induced-matching partition of a graph G having a perfect matching is a k-partition （V1, V2,……, Vk） of V （G） such that for each i （1 ≤ i ≤ k）, the subgraph G [Vi] of G induced by Vi is 1-regular. The k-induced-matching partition problem asks whether a given graph G has a k-inducedmatching partition or not. Let M1,M2,... Mk be k induced matching of G. We say {M1, M2,..., Mk} is a k-induced-matching cover of G if V（M1） U V（M2） U... U V（Mk） = V（G）. The k-induced-matching cover problem asks whether a given graph G has a k- induced-matching cover or not. In this paper, 2-induced-matching partition problem and 2-induced-matching cover problem of graphs with diameter 5 are proved to be NP- complete, which gives a solution of Yang Yuan and Dong.

关 键 词：运筹学 导出匹配 导出匹配划分 导出匹配覆盖 NP-完全 

分 类 号：O157.5[理学—数学] O153.1[理学—基础数学]