直径为2的无爪图的导出匹配可扩性  

Induced Matching Extendability of Claw-free Graphs of Diameter 2

作　　者：徐华锋[1] 李建民[2] 

机构地区：[1]平顶山工学院,河南平顶山467001 [2]平顶山学院,河南平顶山467002

出　　处：《平顶山学院学报》2007年第2期66-68,共3页Journal of Pingdingshan University

摘　　要：研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的.In this paper, the induced matching extendability of claw- free graphs of diameter 2 is studied. We show that a slaw - free graph G of diameter 2 is IM - extendable if and only if, for any induced maching M with ｜M｜ ≤3 of G G- V（M） has no odd component. Consequently,the IM- extendablity problem of claw- free graphs of diameter 2 is polynomially solvable.

关 键 词：无爪图 导出匹配 可扩的 直径 

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