Degree and connectivity conditions for IM-extendibility and vertex-deletable IM-extendibility

作者：Zhang, Xiaoyan^*; Zhang, Zan Bo; Lu, Xiaoxu; Li, Jing

来源：Ars Combinatoria, 2010, 95: 437-444.

• induced matching
• IM-extendable
• 2k-vertex deletable IM-extendable

A graph is called induced matching extendable, if every induced matching of it is contained in a perfect matching of it. A graph G is called 2k-vertex deletable induced matching extendable, if G - S is induced matching extendable for every S subset of V(G) with vertical bar S vertical bar = 2k. The following results are proved in this paper. (1) If k(G) >= inverted right perpendicularv(G)/3inverted left perpendicular 1 and max{d(u), d(v)} >= 2v(G) 1/3 for every two nonadjacent vertices u and v, then G is induced matching extendable. (2) If k(G) >= inverted right perpendicularv(G) 4k/3inverted left perpendicular 1 max{d(u), d(v)} >= 2v(G) 2k 1/3 for every two nonadjacent vertices u and v, then G is 2k-vertex deletable induced matching extendable. (3) If d(u) d(v) >= 2inverted right perpendicularv2v(G) 2k/3inverted left perpendicular - 1 for every two nonadjacent vertices u and v, then G is 2k-vertex deletable IM-extendable. Examples are given to show the tightness of all the conditions.

• 出版日期2010-4
• 单位郑州航空工业管理学院; 南京师范大学; 郑州铁路职业技术学院; 广东轻工职业技术学院