Some results on the matching extendability of graphs in surfaces

Abstract

A connected graph G with at least 2k + 2 vertices is said to be k-extendable if it contains a matching of size k and every such matching can be extended to a perfect matching of G. Aldred et al. showed that for any connected graph G with genus g (resp., non-orientable genus g), if |V(G)| ≥ 8_g-7 (resp., |V(G)| ≥ 4g-7), then G is not 4-extendable [On the matching extendability of graphs in surfaces, J. Combin. Theory Ser. B 98 (2008) 105-115]. In this paper we show that both bounds are sharp and give a generalization: If |V(G)| ≥ ⌊ 8g-8/k-3⌋+ 1 (resp., |V(G)| ≥ ⌊ 4g-8/k-3 ⌋ + 1), then G is not k-extendable for every integer k ≥ 4. Further, we prove that the lower bounds are sharp for the case k = 5.