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 (The matching extendability of surfaces, J. Combin. Theory Ser. B 54 (1992), 133--141) 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 $ρ(Σ)$.

No reviews yet.

No comments yet.