A result on extendibility in the powers of graphs

Let G be a graph on p vertices. Then for a positive integer n , G is said to be n ‐extendible if (i) n < p /2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G . The purpose of this article is to show that if G 2 k is n ‐extendible, for some k  ∈ ℕ, then so is G 2 k +1 , where G q is the graph with the same vertex set as G and in which two vertices u and v are adjacent if and only if d G ( u , v ) ≤ q . We will also show that if G k is 1‐extendible then so is G k +1 . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 1–22, 2007