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

给定一个简单图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-完全的.