×

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.)
PDF BibTeX XML Cite
Full Text: EuDML