**
MATHEMATICA BOHEMICA, Vol. 122, No. 3, pp. 249-255 (1997)
**

#
On $r$-extendability of the hypercube $Q_n$

##
Nirmala B. Limaye, Dinesh G. Sarvate

* Nirmala B. Limaye*, Department of Mathematics, University of Mumbai, India; * Dinesh G. Sarvate*, Department of Mathematics, University of Charleston, S. C., U.S.A

**Abstract:** A graph having a perfect matching is called $r$-extendable if every matching of size $r$ can be extended to a perfect matching. It is proved that in the hypercube $Q_n$, a matching $S$ with $ |S|\leq n$ can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, $Q_n$ is $r$-extendable for every $r$ with $1\leq r\leq n-1.$

**Keywords:** 1-factor, $r$-extendability, hypercube

**Classification (MSC2000):** 05C70

**Full text of the article:**

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]

*
© 1999--2000 ELibM for
the EMIS Electronic Edition
*