Some Studies On The (n,k)-extendable Graphs In Surfaces

There are two components extending the theory of perfect matching, that is, matching extendibility and factor-criticality. Dean obtained the graceful formula of the minimum non-negative integer μ(Σ) such that no graph embeddable in surface Σ is μ(Σ)-extendable. Later, Su and Zhang, Plummer and Zha deduced the minimum non-negative integer ρ(Σ) such that none of Σ-embeddable graph is ρ(Σ)-factor-critical. By counting these two parameters simultaneously, Lu and Wang established the pleasurable formula of the minimum number k=μ(n, Σ) such that no Σ-embeddable graph is an (n,k)-extendable graph by fixing the parameter n.This paper considers two aspects. On one hand, we make the other parameter k fixed and figure out the minimum number n=ρ(k,Σ) such that no graph embeddable in the surface Σ is an (n,k)-extendable graph. On the other hand, let Σ be any surface other than the Sphere and the Projective plane. We talk about an upper bound of the order of Σ-embeddable (n,k)-extendable graphs with 2n+4k> 11 but (n,k)≠ (0,3), (0,4), and find out the necessary and sufficient condition that the number of (n,k)-extendable graphs in Σ are finite if and only if 2n+4k> 11 or (n,k)=(0,3).