Previous |  Up |  Next


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:
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 Size Format View
MathBohem_122-1997-3_4.pdf 499.8Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo