Matching Extension and the Genus of a Graph.

摘要

Let G be a graph with p points having a perfect matching and suppose n is a positive integer with n < or = (p-2)/2. Then G is n-extendable if every matching in G containing n lines is a subset of a perfect matching. In this paper we obtain an upper bound on the n-extendability of a graph in terms of its genus. Keywords: Euler contributions; Theorems. (Author)