Surface embedding of (n, k) -extendable graphs

This paper is concerned with the surface embedding of matching extendable graphs. There are two directions extending the theory of perfect matchings, that is, matching extendability and factor-criticality. In solving a problem posed by Plummer, Dean (1992) established the fascinating formula for the minimum number k=μ(σ) such that everyσ-embeddable graph is not k-extendable. Su and Zhang, Plummer and Zha found the minimum number n=ρ(σ) such that every σ-embeddable graph is not n-factor-critical. Based on the notion of (n,k)-graphs which associates these two parameters, we found the formula for the minimum number k=μ(n,σ) such that every σ-embeddable graph is not an (n,k)-graph. To access this two-parameter-problem, we consider its dual problem and find out μ(n,σ) conversely. The same approach works for rediscovering the formula of the number ρ(σ).