# Article

 Title: On $r$-extendability of the hypercube $Q\sb n$ (English) Author: Limaye, Nirmala B. Author: Sarvate, Dinesh G. Language: English Journal: Mathematica Bohemica ISSN: 0862-7959 (print) ISSN: 2464-7136 (online) Volume: 122 Issue: 3 Year: 1997 Pages: 249-255 Summary lang: English . Category: math . 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.$ (English) Keyword: hypercube Keyword: perfect matching Keyword: 1-factor Keyword: $r$-extendability MSC: 05C70 idZBL: Zbl 0898.05057 idMR: MR1600640 DOI: 10.21136/MB.1997.126151 . Date available: 2009-09-24T21:26:01Z Last updated: 2020-07-29 Stable URL: http://hdl.handle.net/10338.dmlcz/126151 . Reference: [1] N. B. Limaye, Mulupury Shanthi C. Rao: On 2-extendability of generalized Petersen graphs.Math. Bohem. 121 (1996), 77-81. MR 1388178 Reference: [2] Tsuyoshi Nishimura: A theorem on n-extendable graphs.Ars Combinatoria 38 (1994), 3-5. MR 1310401 Reference: [3] M. D. Plummer: On n-extendable graphs.Discrete Math. 31 (1980), 201-210. Zbl 0442.05060, MR 0583220, 10.1016/0012-365X(80)90037-0 Reference: [4] G. Schrag, L. Cammack: On the 2-extendability of the generalized Petersen graphs.Discrete Math. 78 (1989), 169-177. Zbl 0723.05086, MR 1020660, 10.1016/0012-365X(89)90174-X .

## Files

Files Size Format View
MathBohem_122-1997-3_4.pdf 499.8Kb application/pdf View/Open

Partner of