Equimatchable Graphs on Surfaces

Abstract: A graph

G

is equimatchable if any matching in

G

is a subset of a maximum-size matching. It is known that any

2

-connected equimatchable graph is either bipartite or factor-critical. We prove that for any vertex

v

of a

2

-connected factor-critical equimatchable graph

G

and a minimal matching

M

that isolates

v

the graph

G s e t m i n u s (M c u p v)

is either

K_{2 n}

or

K_{n, n}

for some

n

. We use this result to improve the upper bounds on the maximum size of

2

-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus

g

to

4 s q r t g + 17

if

g l e 2

and to

12 s q r t g + 5

if

g g e 3

. Moreover, for any nonnegative integer

g

we construct a

2

-connected equimatchable factor-critical graph with genus

g

and more than

4 s q r t 2 g

vertices, which establishes that the maximum size of such graphs is

T h e t a (s q r t g)

. Similar bounds are obtained also for nonorientable surfaces. Finally, for any nonnegative integers

g

,

h

and

k

we provide a construction of arbitrarily large

2

-connected equimatchable bipartite graphs with orientable genus

g

, respectively nonorientable genus

h

, and a genus embedding with face-width

k

.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Equimatchable Graphs on Surfaces