Some results on the matching extendability of graphs in surfaces
Li, QL, WW Liu, Heping Zhang, Zhang, HP (reprint author), Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China. · Lanzhou University Institutional Repository · 2016
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) over bar), if vertical bar V(G)vertical bar >= 8g-7 (resp., vertical bar V(G)vertical bar > 4 (g) over bar -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 vertical bar V(G)vertical bar >= [8g-8/k-3] + 1 (resp., vertical bar V(G)vertical bar >= [4 (g) over bar -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.