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

摘要

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.%Given a simple graph G and a positive integer fc, a fc-induced-matching partition of a graph G having a perfect matching is a fc-partition (Vi, V2,..., Vk) of V (G) such that for each i (1 i fc), the subgraph G [Vi] of G induced by Vi is 1-regular. The fc-induced-matching partition problem asks whether a given graph G has a fc-induced-matching partition or not. Let Mi,Mi,...Mk be fc induced matching of G. We say {Mi,M2,..., Mk} is a fc-induced-matching cover of G if V(MX) U V(M2)∪...∪V(Mk) = V(G)- The fc-induced-matching cover problem asks whether a given graph G has a fc-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.