On the restricted matching extension of graphs in surfaces

Abstract: A connected graph

G

with at least

2 m + 2 n + 2

vertices is said to have property

E (m, n)

if, for any two disjoint matchings

M

and

N

of size

m

and

n

respectively,

G

has a perfect matching

F

such that

M s u b s e t e q F

and

N c a p F = v a r n o t h i n g

. In particular, a graph with

E (m, 0)

is

m

-extendable. Let

m u (S i g m a)

be the smallest integer

k

such that no graphs embedded on a surface

S i g m a

are

k

-extendable. Aldred and Plummer have proved that no graphs embedded on the surfaces

S i g m a

such as the sphere, the projective plane, the torus, and the Klein bottle are

E (m u (S i g m a) - 1, 1)

. In this paper, we show that this result always holds for any surface. Furthermore, we obtain that if a graph

G

embedded on a surface has sufficiently many vertices, then

G

has no property

E (k - 1, 1)

for each integer

k g e q 4

, which implies that

G

is not

k

-extendable. In the case of

k = 4

, we get immediately a main result that Aldred et al. recently obtained.

Recommendations

Cites Work

Cited In (9)

This page was built for publication: On the restricted matching extension of graphs in surfaces