| 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 |
| . |
