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 (MSC 1991): 05C70

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).