Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
hypercube; perfect matching; 1-factor; $r$-extendability
hypercube; perfect matching; 1-factor; $r$-extendability
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.$
References:
[1] N. B. Limaye, Mulupury Shanthi C. Rao: On 2-extendability of generalized Petersen graphs. Math. Bohem. 121 (1996), 77-81. MR 1388178
[2] Tsuyoshi Nishimura: A theorem on n-extendable graphs. Ars Combinatoria 38 (1994), 3-5. MR 1310401
[3] M. D. Plummer: On n-extendable graphs. Discrete Math. 31 (1980), 201-210. DOI 10.1016/0012-365X(80)90037-0 | MR 0583220 | Zbl 0442.05060
[4] G. Schrag, L. Cammack: On the 2-extendability of the generalized Petersen graphs. Discrete Math. 78 (1989), 169-177. DOI 10.1016/0012-365X(89)90174-X | MR 1020660 | Zbl 0723.05086
Search
Partner of
