Matchings and matching extensions in graphs Original Research Article

Let G be a graph with a perfect matching and k be an integer such that 1 ⩽ k < vbV(G)vb/2. Then G is said to be k-extendable if every matching of size k in G extends to a perfect matching of G. Plummer (1994) proved that every (2k + 1)-connected K1,3-free graph of even order is k-extendable. In this paper, it was proved that every (2k + n − 2)-connected K1,n-free graph of even order is k-extendable. Also, an answer to the problem of characterizing maximal k-extendable graphs posted by Plummer (1994) and Saito (1989/90) is given. Besides, we show that a regular graph of even order belongs to the first class if its any two odd cycles have at least a vertex in common.