On the restricted matching of graphs in surfaces

Original · EN

A connected graph G with at least 2m+2n+2 vertices is said to have property E(m,n) if, for any two disjoint matchings M and N of size m and n respectively, G has a perfect matching F such that M F and N∩ F=. In particular, a graph with E(m,0) is m-extendable. Let μ(Σ) be the smallest integer k such that no graphs embedded on a surface Σ are k-extendable. Aldred and Plummer have proved that no graphs embedded on the surfaces Σ such as the sphere, the projective plane, the torus, and the Klein bottle are E(μ(Σ)-1,1). In this paper, we show that this result always holds for any surface. Furthermore, we obtain that if a graph G embedded on a surface has sufficiently many vertices, then G has no property E(k-1,1) for each integer k≥ 4, which implies that G is not k-extendable. In the case of k=4, we get immediately a main result that Aldred et al. recently obtained.