论文部分内容阅读
给定一个简单图G和正整数k，具有完美匹配的图G的k-导出匹配划分是对顶点集V（G）的一个k-划分（V1，V2,…，Vk），其中对每一个i（1≤i≤k），由Vi导出的G的子图G[Vi]是1-正则的．k-导出匹配划分问题是指对给定的图G，判定G是否存在一个k-导出匹配划分．令M1，M2…，Mk为图G的k个导出匹配，如果V（M1）U（M2）U…UV（Mk）=V（G），则我们称{M1，M2…．，Mk）是G的k-导出匹配覆盖．k-导出匹配覆盖问题是指对给定的图G，判定G是否存在k-导出匹配覆盖．本文给出了Yang，