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

摘要

@@Cameron和Faudree等人在1989年对导出匹配的基本性质和存在性条件进行了研究。导出匹配划分问题早出现在组合优化领域。由Yuan， Wang和Yang对该问题进行了研究，得到了一些有意义的结果。导出匹配覆盖问题由Dong和Yuan在2006年提出。对于上述两问题的研究，目前结论还不是很多。本文将证明直径为3的图的导出匹配3-划分和导出匹配3-覆盖都是NP-完全的。