Connectivity of k-extendable graphs with large k

Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0 less than or equal to k less than or equal to n - 1), G is k-extendable if any matching of size k in G is contained in a perfect matching of G. It is proved that if G is a k-extendable graph on 2n vertices with k greater than or equal to n/2, then either G is bipartite or the connectivity of G is at least 2k. As a corollary, we show that if G is a maximal k-extendable graph on 2n vertices with n + 2 less than or equal to 2k + 1, then G is K-n,K-n if k + I less than or equal to delta less than or equal to n and G is K-2n if 2k + 1 less than or equal to delta less than or equal to 2n - 1. Moreover, if G is a minimal k-extendable graph on 2n vertices with n + 1 less than or equal to 2k + I and k + I less than or equal to delta less than or equal to n then the minimum degree of G is k + 1. We also discuss the relationship between the k-extendable graphs and the Hamiltonian graphs. (C) 2003 Elsevier B.V. All rights reserved.