CAJ | 학술논문

给定一个简单图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-完全的.
급정일개간단도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.