摘要
图Ｇ的一个匹配Ｍ是导出的，若Ｍ是图Ｇ的一个导出子图．图Ｇ是导出匹配可扩的（简记ＩＭ－可扩的），若图 Ｇ的任一导出匹配均含于图 Ｇ的一个完美匹配当中．本文我们将证明如下结果． （１）对无爪图而言，问题“给定图Ｇ以及一个正整数ｒ，确定是否存在图Ｇ的一个导出匹配Ｍ使得｜Ｍ｜≥ｒ”是ＮＰ－完全的． （２）对直径为２的图以及直径为３的偶图，问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ－完全的；而对完全多部图而言，该问题线性可解。
A matching M of a graph G is induced, if M is an induced subgraph of G. A graph G is induced matching extendable (simply IM-extendable), if every induced matching M of G is included in a perfect matching of G. In this paper we will prove the following results. (1) The problem 'given a graph G and a positive integer r, determine whether there is an induced matching M of G such that |M|≥r' is NP-complete for claw-free graphs. (2) The problem 'determine whether a given graph is IM-extendable' is co-NP- complete for graphs with diameter 2 and bipartite graphs with diameter 3 but linearly solvable for complete multi-partite graphs.
出处
《运筹学学报》
CSCD
2000年第1期76-80,共5页
Operations Research Transactions
基金
National Natural Science Foundation of China
the Excellent Young Foundation of Henan Province.
