On the restricted matching of graphs in surfaces

Details On the restricted matching of graphs in surfaces On the restricted matching of graphs in surfaces

2010-02-03

arxiv.org/abs/1002.0661v1

Mathematics

Combinatorics

9 pages

Scientific paper

A connected graph $G$ with at least $2m+2n+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\subseteq F$ and $N\cap F=\varnothing$. In particular, a graph with $E(m,0)$ is $m$-extendable. Let $\mu(\Sigma)$ be the smallest integer $k$ such that no graphs embedded on a surface $\Sigma$ are $k$-extendable. Aldred and Plummer have proved that no graphs embedded on the surfaces $\Sigma$ such as the sphere, the projective plane, the torus, and the Klein bottle are $E(\mu(\Sigma)-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\geq 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.

Affiliated with

Also associated with

No associations

Rating

On the restricted matching of graphs in surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the restricted matching of graphs in surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the restricted matching of graphs in surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-601596