, Let xy be that contained edge)-(5) that there is no bad configuration (w, z, M R ) in Q R such that w L and z L are both incident with e 1 or e 2 Thus the configuration Hence there is a Hamiltonian path The desired Hamiltonian path of Q 4 ? M is P ux + P x R y R + P yv where P ux and P yv are disjoint subpaths of P uv , assuming that x is closer to u than y on the path P uv . Case 3: m(M ) = 2 Applying Lemma 9 observe that Figure 24(1)-(4) shows all bad configurations in Q L or Q R for each of the four maximal unaligned matchings M with m(M ) = 2 depicted in Figure 8, respectively. Subcase 3.1: Vertices u and v are separated Assume that u ? V (Q L ) and v ? V (Q R ) We distinguish the following three possibilities. 3.1.1: M is as in Figure 24(1) and u or v is incident with M d . Assume that u = a, the other case is symmetric. Observe in Figure 25 that the statement holds for each v ? V (Q R ) of different parity than u. 3.1.2: M is as in Figure 24(4) and {u, v} = {d, e}. Observe in Figure 26 that the statement holds. 3.1.3: The remaining possibilities; that is, M is as in Figure 24(1) and none of u and v is incident with M d , or M is as in Figure)-(4) and {u, v} = {d, e}. A vertex w ? V (Q L ) is free if it has a different parity than u and is not incident with M d . We claim that there is a free vertex w ? V (Q L ) such that the configurations Observe from the same figure that the configuration (u, x, M L ) is bad for at most one free vertex x. Similarly, the configuration (v, y R , M R ) is bad for at most one free vertex, we have four free vertices. References [1] R. CAHA, V. KOUBEK, Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. Graph Theory, pp.51-53, 2005.
, On the Existence of Hamiltonian Circuits in Faulty Hypercubes, SIAM Journal on Discrete Mathematics, vol.4, issue.4, pp.511-527, 1991.
DOI : 10.1137/0404045
, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math, vol.19, pp.135-144, 2005.
, Hamiltonian paths with prescribed edges in hypercubes, Discrete Mathematics, vol.307, issue.16, pp.1982-1998, 2007.
DOI : 10.1016/j.disc.2005.12.045
, Perfect matchings extend to Hamilton cycles in hypercubes, Journal of Combinatorial Theory, Series B, vol.97, issue.6, pp.1074-1076, 2007.
DOI : 10.1016/j.jctb.2007.02.007
, Smallest maximal matchings in the graph of the d-dimensional cube, Journal of Combinatorial Theory, Series B, vol.14, issue.2, pp.153-156, 1973.
DOI : 10.1016/0095-8956(73)90059-2
, Pulse Code Communication, U.S. Patent 2,632,058, filed 13, 1947.
, On Hamiltonian circuits and spanning trees of hypercubes, ? Cas, P?st. Mat, vol.109, pp.135-152, 1984.
, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl, vol.16, pp.87-91, 1996.
, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, 1992.
, Hyper-Hamilton Laceable and Caterpillar-Spannable Product Graphs, Computers & Mathematics with Applications, vol.34, issue.11, pp.99-104, 1997.
DOI : 10.1016/S0898-1221(97)00223-X
URL : http://doi.org/10.1016/s0898-1221(97)00223-x
, Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $, SIAM Journal on Discrete Mathematics, vol.6, issue.1, pp.152-166, 1993.
DOI : 10.1137/0406012
, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science, vol.314, issue.3, pp.431-443, 2004.
DOI : 10.1016/j.tcs.2004.01.035
, Fault-tolerant hamiltonian laceability of hypercubes, Information Processing Letters, vol.83, issue.6, pp.301-306, 2002.
DOI : 10.1016/S0020-0190(02)00214-4