郑州大学学报（理学版）2003，Vol.35Issue(3)：12-15,4.
直径为2的无爪图的导出匹配可扩性
Induced Matching Extendability of Claw-free Graphs of Diameter 2
摘要
Abstract
A simple graph G is induced matching extendable,shortly IM-extendable,if every induced matching of G is included in a perfect matching of G.The induced matching extendability of claw-free graphs of diameter 2 is studied.It is shown that a claw-free graph G of diameter 2 is IM-extendable if and only if,for any induced matching M with |M|≤3 of G,G-V(M) has no odd component.Consequently,the IM-extendability problem of claw-free graphs of diameter 2 is polynomially solvable.
关键词
匹配/完美匹配/导出匹配/IM-可扩的/无爪图Key words
matching/perfect matching/induced matching/IM-extendable/claw-free
分类
数理科学引用本文复制引用
周菊,要卫丽,鲁晓旭..直径为2的无爪图的导出匹配可扩性[J].郑州大学学报（理学版）,2003,35(3):12-15,4.
