小直径图的导出匹配覆盖(英文)

Cover a Graph with Small Diameter by Induced Matchings

设G是一个图,而M_1,M_2,…,M_k是G的k个导出匹配.称{M_1,M_2,…,M_k)是图G的一个k-导出匹配覆盖,若V(M_1)∪V(M_2)∪…∪V(M_k)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.

Let G be a graph and M1,M2,…,Mk are k induced matchings of G. We say {M1,M2,…,Mk） is a k-induced-matching cover of G if V（M1）∪V（M2）∪…∪V（Mk）=V（G）. The k-induced-matching cover problem asks whether a given graph G has a k-induced-matching cover or not. This paper shows that 2-induced-matching cover problem of graphs with diameter 6 and 3-induced-matching cover problem of graphs with diameter 2 are NP-complete, and 2-induced-matching cover problem of graphs with diameter 2 is polynomially solvable.