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: