## On $$r$$-extendability of the hypercube $$Q_n$$.(English)Zbl 0898.05057

Summary: 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$$.

### MSC:

 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

### Keywords:

1-factor; $$r$$-extendability; hypercube; perfect matching
Full Text: