Degree Sum Conditions of Induced Matching Extendable Graphs
Qin Wang · 2000
Say that a simple graph G is induced matching extendable, shortly IM extenable, if every induced matching of G is included in a perfect matching of G . Degree sum conditions of IM extendable graphs are researched. The main results are as follows: (1) Let G be a graph with 2n vertices. If for each pair of nonadjacent vertices u and v in G , d(u)+d(v)≥2[4n3]-1 , then G is IM extendable. (2) Let G be a claw free graph with 2n vertices. If for each pair of nonadjacent vertices u and v in G,d(u)+d(v)≥2n+3, then G is IM extendable. It is also shown that these results are best possible.