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).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
