Geodesic
On $r$-extendability of the hypercube $Q\sb n$
Mathematica Bohemica, Tome 122 (1997) no. 3, pp. 249-255

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.$
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.$
DOI : 10.21136/MB.1997.126151
Classification : 05C70
Keywords: hypercube; perfect matching; 1-factor; $r$-extendability 
Limaye, Nirmala B.; Sarvate, Dinesh G. On $r$-extendability of the hypercube $Q\sb n$. Mathematica Bohemica, Tome 122 (1997) no. 3, pp. 249-255. doi: 10.21136/MB.1997.126151
@article{10_21136_MB_1997_126151,
     author = {Limaye, Nirmala B. and Sarvate, Dinesh G.},
     title = {On $r$-extendability of the hypercube $Q\sb n$},
     journal = {Mathematica Bohemica},
     pages = {249--255},
     year = {1997},
     volume = {122},
     number = {3},
     doi = {10.21136/MB.1997.126151},
     mrnumber = {1600640},
     zbl = {0898.05057},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126151/}
}
TY  - JOUR
AU  - Limaye, Nirmala B.
AU  - Sarvate, Dinesh G.
TI  - On $r$-extendability of the hypercube $Q\sb n$
JO  - Mathematica Bohemica
PY  - 1997
SP  - 249
EP  - 255
VL  - 122
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126151/
DO  - 10.21136/MB.1997.126151
LA  - en
ID  - 10_21136_MB_1997_126151
ER  - 
%0 Journal Article
%A Limaye, Nirmala B.
%A Sarvate, Dinesh G.
%T On $r$-extendability of the hypercube $Q\sb n$
%J Mathematica Bohemica
%D 1997
%P 249-255
%V 122
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126151/
%R 10.21136/MB.1997.126151
%G en
%F 10_21136_MB_1997_126151

[1] N. B. Limaye, Mulupury Shanthi C. Rao: On 2-extendability of generalized Petersen graphs. Math. Bohem. 121 (1996), 77-81. | MR

[2] Tsuyoshi Nishimura: A theorem on n-extendable graphs. Ars Combinatoria 38 (1994), 3-5. | MR

[3] M. D. Plummer: On n-extendable graphs. Discrete Math. 31 (1980), 201-210. | DOI | MR | Zbl

[4] G. Schrag, L. Cammack: On the 2-extendability of the generalized Petersen graphs. Discrete Math. 78 (1989), 169-177. | DOI | MR | Zbl

Cité par Sources :