Let G be a graph on p vertices. Then for a positive integer n, G is said to be n-extendible if (i) TI < p / 2 , iii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is TIconnected, then Gk is ([$?] -1)-extendible for every integer k 2 2 such that [$] -1 < p / 2 . 0 1996 John Wiley &Sons, Inc.
Let G be a graph whose vertex set is V(G) and whose edge set is E(G). We will use p to stand for IV(G)l, and (throughout this paper) we will assume that G has no loops or multiple edges. Two edges are independent if they have no common endpoint, and a matching M in G is a set of (pairwise) independent edges. A matching M is a perfect matching if every vertex in G is an endpoint of one of the edges in M , and M will be called extendible if it is contained in some perfect matching in G. We will use the definition of n-extendibility as stated in Yu's 1993 paper [6]. G will be called n-extendible for a positive integer n, if (i) n < p / 2 , (ii) G has a matching of size n, and (iii) every such matching is extendible in G. A graph G will be called 0-extendible if G has a perfect matching.
We will use &(u, w) to denote the length of a shortest upath in G. If Ic is a positive integer, then Gk will denote the graph whose vertex set is V(G) and in which two vertices u and w are adjacent if and only if dc(u, w) 5 k . *This research was completed as part of a doctoral dissertation while under the supervision of Dr. David P. Sumner.