直径为2的无爪图的导出匹配可扩性(英文)  

Induced Matching Extendability of Claw-free Graphs of Diameter 2

作　　者：周菊[1] 要卫丽[1] 鲁晓旭[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《郑州大学学报（理学版）》2003年第3期12-15,共4页Journal of Zhengzhou University:Natural Science Edition

摘　　要：如果简单图G的每一个导出匹配都包含在它的一个完美匹配中 ,称图G是导出匹配可扩的 ,简称为IM 可扩的 .研究了直径为 2的无爪图的导出匹配性 ,证明了一个直径为 2的无爪图G是IM 可扩的充分必要条件是 :对任意满足 |M|≤ 3的导出匹配M ,G -V(M)没有奇分支 .因而 ,直径为 2的无爪图的IMA 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-可扩 多项式可解 图论 

分 类 号：O157.5[理学—数学]