Abstract
A graph G with at least 2n + 2 vertices is said to he n-extendable if every set of n disjoint edges in G extends to (i.e.. is a Subset of) a perfect matching. More generally, a graph is said to have property E(m, n) if, for every matching M of size in and every matching, N of size n in G such that M boolean AND N = theta, there is a perfect matching F in G Such that M subset of F, but F boolean AND N = theta. G is said to have property E(0, 0) if it has a perfect matching. The Study of the properties E(m,n) is referred to as the study of restricted matching extension.
In [M. Porteous, R. Aldred, Matching extensions with prescribed and forbidden edges, Australas. J. Combin. 13 (1996) 163-174 M. Porteous, Generalizing matching extensions, M.A. Thesis, University of Otago, 1995; A. McGregor-Macdonald, The E(m,n) property, M.Sc. Thesis, University of Otago, 2000], Porteous and Aldred, Porteous and McGregor-Macdonald, respectively, Studied the possible implications among the properties E(m,n) For Various values of m and n. In an earlier paper [R.E.L. Aldred, Michael D. Plummer, On restricted matching extension in planar graphs, in: 17th British Combinatorial Conference (Canterbury 1999), Discrete Math. 231 (2001) 73-79], the present authors completely determined which of the various properties E(m. n) always hold, sometimes hold and never hold tor graphs embedded in the plane. In the present paper. we do the same for embeddings in the projective plane, the torus and the Klein bottle. (C) 2007 Elsevier B.V All rights reserved.