IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1158 ISSN 2232-2094 ON THE MUTUALLY INDEPENDENT HAMILTONIAN CYCLES IN FAULTY HYPERCUBES Vida Vukasinovic Petr Gregor Riste Skrekovski Ljubljana, September 6, 2011 vo $H CD rO CD ¡5 CO CO On the mutually independent Hamiltonian cycles in faulty hypercubes* Vida Vukasinovic Petr Gregor 2, Riste Skrekovski 3 CD March 26, 2011 1 Computer Systems Department, Jozef Stefan Institute, Jamova 39, 1000 Ljubljana, Slovenia vida.vukasinovic@ijs.si 2 Department of Theoretical Computer Science and Mathematical Logic, Charles University, Malostranske nam. 25, 11800 Prague, Czech Republic gregor@ktiml.mff.cuni.cz 3 Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia skrekovski@gmail.com CM Abstract Two ordered Hamiltonian paths in the n-dimensional hypercube Qn are said to be independent if i-th vertices of the paths are distinct for every 1 < i < 2n. Similarly, two s-starting Hamiltonian cycles are independent if i-th vertices of the cycle are distinct for every 2 < i < 2n. A set S of Hamiltonian paths and s-starting Hamiltonian cycles are mutually independent if every two paths or cycles, respectively, from S are independent. We show that for every set F of f edges and n — f pairs of adjacent vertices wi and bi, there are n — f mutually independent Hamiltonian paths with endvertices wi, bi and avoiding edges of F in Qn. We also show that Qn contains n — f fault-free mutually independent s-starting Hamiltonian cycles, for every set of f < n — 2 faulty edges in Qn and every vertex s. This improves previously known results on the numbers of mutually independent Hamiltonian paths and cycles in the hypercube with faulty edges. Jh CD Keywords: hypercube, Hamiltonian path, Hamiltonian cycle, faulty edges, interconnection network *This research was supported by the Czech-Slovenian bilateral grant MEB 090805 and BI-CZ/08-09-005, by the Czech Science Foundation Grant 201/08/P298, and by ARRS Research Program P1-0297. 1 1 Introduction 00 lO C r A parallel computer network is often modeled as an undirected graph in which the vertices correspond to processors and the edges correspond to communication links between the processors. Graphs which represent topological structure of parallel computer networks are required to posses elegant properties such as small degree and diameter, high connectivity, recursive structure, symmetry, etc. Moreover, one of the major concerns of the parallel network design is its robustness, i.e. tolerance to the occurence of faults. Failures could happen in hardware, software or even because of missing transmitted packet. In this paper we study a fault tolerance of the hypercube, one of the most popular architectures which CO has all above mentioned properties. The n-dimensional hypercube Qn is a (bipartite) graph with all binary vectors of length n as vertices, and with edges between every two vertices that differ in exactly one coordinate. Connection failures in computer network correspond to faulty edges in the underlying graph. It is important that network stays highly connected even if several connection failures appear. For this reason, mutually independent Hamiltonian paths/cycles of Qn with arbitrarily chosen f faulty edges are studied. In this paper, n always denotes a positive integer and [n] denotes the set {1, 2,... ,n}. A path in the graph G is a sequence P = (vi,v2,... ,vk) of distinct vertices such that every two consecutive vertices are adjacent. For a path P = (vi ,v2,..., vk) we say that vi and vk are the endvertices of P, and that P is a vivk-path, which is denoted by P[vi,vk]. A path in G is Hamiltonian if it contains all vertices of G. Let V(G) and E(G) denote the vertex set and the edge set of a graph G, respectively, and let m = ¡V(G)|. Two Hamiltonian paths Pi = (ui,u2,..., um) and P2 = (vi,v2,..., vm) of G are independent if ui = vi for all i G [m]. A set S of Hamiltonian paths of G is mutually independent if every two paths from S are independent. A study of such paths is motivated by the problem of simultaneous transmitting packets along these path such that they never meet in the same vertex. A cycle is a sequence C = (vi,v2,... ,vk) of k > 3 distinct vertices such that every two consecutive vertices, including the first and the last vertex of the sequence are adjacent. We say that the cycle C = (vi,v2,... ,vk) is v^starting to emphasize the first vertex vi and we denote it by C[vi]. A cycle C in a graph G is Hamiltonian, if it contains all vertices of G. Two v-starting Hamiltonian cycles Ci = (v, u2,..., um) and C2 = (v,v2,..., vm) are independent if vi = ui for all 2 < i < m. A set S of v-starting Hamiltonian cycles of G is mutually independent if every two cycles from S are independent. A study of mutually independent v-starting Hamiltonian cycles is motivated by the problem of transferring different pieces of a given message from one node to all recipients simultaneously such that they never meet in the same node. In 2005, Sun, Lin, Huang and Hsu [10] proved that for any vertex s, the n-dimensional hypercube Qn contains n— 1 mutually independent s-starting Hamiltonian cycles if n = 2, 3; and n mutually independent s-starting Hamiltonian cycles if n > 4. They also proved that for any set of n — 1 distinct pairs of adjacent vertices, Qn contains n — 1 mutually independent Hamiltonian paths with these pairs of vertices as endvertices. In 2006, Hsieh and Yu [4] claimed that the n-dimensional hypercube Qn with at most f < n — 2 faulty CD CO u edges contains a set of n — 1 — f mutually independent Hamiltonian paths and a set of n — 1 — f mutually independent s-starting Hamiltonian cycles for any vertex s. However, in 2007, Kueng, Lin, Liang, Tan and Hsu [6] noticed a flaw in their proof and published the correction. In 2009 Hsieh and Weng [3] proved that for n > 3, Qn with at most f < n — 2 faulty edges contains a set of n — 1 — f mutually independent Hamiltonian paths between any two vertices of different parity. In 2010 Shih, Tan and Hsu [9] studied mutually independent paths of different length in Qn. In this paper, we improve previous known results by showing that Qn contains a set of n — f mutually independent Hamiltonian paths, see Theorem 13. We also prove that Qn with at most f < n — 2 faulty edges contains a set of n — f mutually independent s-starting Hamiltonian cycles for any vertex s, see Theorem 15. This is the optimal result since s may be incident with f faulty edges. a CD D CD CO 00 lO O co CD Jh CD CO u 2 Preliminaries In this section we define notations and summarize previously known results that we use. The distance of two edges e1,e2 E E(G) is the minimal distance between a vertex of e1 and a vertex of e2. Let us say that the edge vivj E E(G) is directed, if we fix the order of its vertices by (vi,vj). We say that a cycle C = (v1,v2,... ,vk) is directed if ViVi+1 are directed edges in C for all i E [k] (where vk+1 = v1). Let Qn be the n-dimensional hypercube. For a vertex v E V(Qn), let vi be the neighbor of v that differs from v exactly in the i-th coordinate. We say that the edge vv% is i-directional. Furthermore, for an edge e = uv we denote e% = uivi. The antipodal vertex to a vertex v differs from v in all coordinates, and is denoted by v. Note that the hypercube Qn is an n-regular graph with 2n vertices. Two vertices of Qn are of the same parity if both of them have even (odd) number CO of 1's. We say the vertex is white (black) if it has even (odd) number of 1's. Note that vertices of each parity form bipartite classes of Qn. Consequently, u and v have the same parity if and only if d(u,v) is even. We say that the edges uiui+1 and UjUj+1 of a directed path or cycle (u1,u2,..., un) have the same parity if ui and uj are of the same parity; that is, i — j = 0 (mod 2). For d E [n] and i E {0,1} let Q^l 1 be the subgraph of Qn induced by the vertices with i on the d-th coordinate. Notice that Q^l 1 is isomorphic to Qn_1. In other words, by removing all edges of the direction d, the hypercube Qn splits into two (induced) subgraphs Qi_1, Qdn_11 isomorphic to Qn_1. We say that Qn is split along the direction d into subcubes Qn- a and Qn_1. Let us write Qin_1 instead of Qn_ 1 if the direction d is clear from the context. Furthermore, we generalize this concept as follows. For {d1,d2,... ,dp} C [n] and (i1,i2,.. .,ip) E {0,1}p let Qn_d-dp^i2'""ip) be the subgraph of Qn induced by all the vertices whose d1-th, d2-th, ..., dp-th coordinate equals to i1,i2,..., ip, respectively. Let us write simply Qin_2^'ip for Q u2j, u2j+1) where the indices are taken cyclically; that is, u2n-i+i = u1. Observe that the k-th vertices, 1 < k < 2n, of P1 and P2 are in distinct subcubes if k is even. If k = 1 (mod 3), they are in the form of u2i+s and u2j+s for some s. If k = 3 (mod 3), they are in the form u^i+s and u^j+s for some s. Thus, since i and j are distinct, the k-th vertices of P1 and P2 are distinct for every 1 < k < 2n. □ Now, we list the results that we need. It is well known that the hypercube Qn is Hamiltonian for every n > 2. It is also Hamiltonian laceable [2]; that is, there is a Hamiltonian path between every two vertices of opposite parity. Even if some faulty edges appear in Qn, the hypercube Qn stays Hamiltonian laceable. CO 00 lO Proposition 2 (Tsai et al. [11]). Let F Ç E(Qn), n > 2 and \F\ < n — 2. Then, there 00 exists a Hamiltonian path in Qn — F between every two vertices of opposite parity. We also need several basic results on Hamiltonian cycles and paths in the hypercube with some removed vertices. The following proposition describes the case of one removed vertex. Proposition 3 (Lewinter and Widulski [7]). For n > 2 and every three distinct vertices u1,u2,v E V(Qn) such that u1,u2 have the same parity opposite to the parity of v E V(Qn), the graph Qn — {v} has a Hamiltonian u1u2-path P. o A similar result holds for the case of two removed vertices. Proposition 4 (Sun et al. [10]). The graph Qn — {u,v}, n > 4 is Hamiltonian laceable for every two vertices u and v of opposite parity. CNI A set M C E(G) of pairwise non-adjacent edges is called a matching. A matching M is perfect if every vertex of G is covered by M. Kreweras [5] conjectured that every perfect matching of the hypercube Qn, where n > 2, can be extended to a Hamiltonian cycle. Fink [1] affirmatively answered this conjecture by proving a stronger result for the complete graph on the vertices of Qn, denoted by K(Qn). Theorem 5 (Fink [1]). For every perfect matching M of K(Qn) where n > 2, there exists a perfect matching N of Qn such that M U N forms a Hamiltonian cycle of K(Qn). CO CO We say that k edges e\,e2,... ,ek E E(Qn) are rigid if they have distinct directions. Note that necessarily k < n. For a set S of edges of Qn, we say that S saturates a vertex v if some edge of S is incident with the vertex v. Otherwise, v is said to be unsaturated by S. Furthermore, we say that a vertex v of Qn is blocked by S if all neighbors of v are CD CD saturated by S and v is not saturated by S. Theorem 6 (Limaye and Sarvate [8]). If a matching M C E(Qn) of size n > 2 does not extend to a perfect matching in Qn, then there is an unsaturated vertex v whose neighborhood is saturated by M. The previous results on mutually independent Hamiltonian paths and cycles in the hypercube are as follows. vO Theorem 7 (Sun et al. [10]). For any s E V(Qn), the hypercube Qn contains n—1 mutually independent s-starting Hamiltonian cycles if 2 < n < 3, and n mutually independent s-starting Hamiltonian cycles if n > 4. s Lemma 8 (Sun et al. [10]). Let wi,w2,..., wn-i be vertices of the same parity in Qn, n > 2 and let {wibi,w2b2,... ,wn-ibn-i} Ç E(Qn) be a matching in Qn. Then, Qn contains n — 1 mutually independent Hamiltonian paths Pi[wvi, bi], P2[w2, b2],..., Pn-i[wn-i, bn-ij. CO Lemma 9 (Kueng et al. [6]). Let F Ç E(Qn), n > 3, f = \F\ < n — 2 and wi,w2,... ,wk be vertices of the same parity in Qn, k < n — 1 — f. Let {wibi,w2b2,... ,wkbk} Ç E(Qn) be a matching in Qn. Then, Qn — F contains k mutually independent Hamiltonian paths Pi[wi,bi], P2[w2,b2], ... ,Pk[wk,bk]. a lO We use Theorem 6, Theorem 7 and Lemma 8 to improve the result by Kueng, Lin, Liang, Tan and Hsu stated in Theorem 10. In the next section, we prove Theorem 13 which is improvement of Lemma 8 then we apply it in Section 4 (Theorem 15) to improve the following result. Theorem 10 (Kueng et al. [6]). Let F C E(Qn), n > 4, f = \F\< n - 2, and s E V(Qn). Then, Qn — F has n — 1 — f mutually independent s-starting Hamiltonian cycles. CM CO 3 Independent Hamiltonian paths in hypercubes We start with an improvement in a special case that follows from Theorem 5. CO Lemma 11. Let wi,w2,... ,wk be vertices of the same parity in Qn, n > 2. If wibi,w2b2,..., wk bk are edges of a perfect matching M of Qn, then Qn has k mutually independent Hamiltonian paths Pi[wi, bi],P2[w2,b2],..., Pk[wk, bk]. Proof. By Theorem 5, there is a Hamiltonian cycle C containing the edges wibi,w2b2,..., wkbk. Moreover, edges wibi,w2b2,..., wkbk have the same parity on C as they are included in the perfect matching M. If we disconnect the cycle C between vertices wi and bi, we obtain a Hamiltonian path Pi[wi, bi] of Qn. As Pi, P2,..., Pk C C and wibi,w2b2,..., wkbk have the same parity on C, Pi and Pj are independent for every distinct i,j E [k]. □ "in Proposition 12. Let Pi be a set of mutually independent Hamiltonian paths in Q^-.i for i = 0,1 and some direction d. Then, the set {Z(P,d); P E V0 U Pi} is a set of mutually independent Hamiltonian paths in Qn. We need the next proposition to prove Theorem 13. Proof. Let Pi,P2 E V0. Then, observe that Z(Pi,d), Z(P2,d) are mutually independent Hamiltonian paths in Qn. Indeed, since every t-th vertex v of Pi and t-th vertex u of P2 are distinct, we infer that vd and ud are distinct and so Z(Pi, d) and Z(P2, d) are independent in Qn. A similar argument holds if Pi, P2 EVi. Now, let Pi EVi for i = 0,1. Then, the claim obviously holds as t-th vertices of Z (P0, d) and Z(Pi, d) are in distinct parts Qdnj-_i and Qdn--i for all t E [2n]. □ 6 The following theorem improves Lemma 8 by one additional independent Hamiltonian path. Theorem 13. Let wi,w2,... ,wn be vertices of the same parity in Qn and let M = {wibi,w2b2,... ,wnbn} C E(Qn) be a matching of Qn (n > 2). Then, Qn has n mutually independent Hamiltonian paths Pi[wi, bi], P2[w2, b2],..., Pn[wn, bn]. Proof. We prove that Qn contains n mutually independent Hamiltonian paths Pi [wi, bi] for i E [n] by induction on the dimension n. The base of induction for Q2 trivially holds since Q2 contains two mutually independent Hamiltonian paths whose first and last vertices are vertices of two independent edges of M, respectively. Now, we assume that the statement holds for Qn-i and we prove it for Qn, n > 3. We consider three cases regarding M. G Case 1: The matching M extends to a perfect matching. Then, Qn has n mutually independent Hamiltonian paths by Lemma 11. o In the remaining two cases, we assume due to Theorem 6 that some vertex v is blocked by M. Case 2: M is not rigid. We proceed similarly as in the proof of Lemma 8 from Sun et. al. [10]. Since M is not rigid, there exists a direction d such that M contains no d- csr directional edge. We split Qn along the direction d and we obtain two subcubes Qn_i and Qn-i. Since there exists v E V(Qn) blocked by M, for some i E {0,1} the subcube Qin-i contains one edge wkbk of M where k E [n] and the subcube Q1— contains all the other edges of M. By induction, there is one Hamiltonian path Pk[wk,bk] in Qin-i and n — 1 mutually independent Hamiltonian paths Pl[wl,bi] in Qn—'i for l E [n] \ {k}. We extend all these Hamiltonian paths Pj to Hamiltonian zigzag paths Z(Pj,d) in Qn, which are mutually independent by Proposition 12. Case 3: M is rigid. First, in case n = 3, there is only one possibility up to isomorphism that the vertex v is blocked by a set of three rigid edges. In this case the example of mutually independent Hamiltonian paths are m CD u CD Pi[wi,bi] = (wi,b,w3,b3,v,b2,w2,bi), P2[w2,b2] = (w2,bi,wi,b,w3,b3,v,b2), P3[w3,b3] = (w3,b2,v,bi,w2,b,wi,b3). 4J as illustrated in Figure 2. Suppose now n > 4. We can assume bi = w\ for every i E [n] as M is a set of n rigid edges. Our aim is the following: We split Qn along an arbitrary direction k E [n] vo $H CD CD a CD CO 00 lO (1, 3, 7) (8, 2, 4) (3, 5,1) W3 b 2 (2,4, 6) (7,1,5)) b Figure 2: Q3 with three mutually independent Hamiltonian paths. Each vertex u of Q3 is associated with a triple (k1,k2,k3) which says that u is the ki-th vertex in the z-th Hamiltonian path Pi[wi,bi]. 0 o 1 CO ^ CO CO into subcubes Q^i and Qll-1. Notice that one of the subcubes 1, Qh-i contains one edge of the matching M and the other subcube contains all the remaining edges except the one which is of direction k. Without loss of generality, we may assume that the vertex v is black and v E V(Q^^)- Then, Q°n-1 contains n — 2 edges of M, and Qln-1 contains ej = Wjbj E M for some j E [n] \ {k} such that Wj = vk. Notice that bk is adjacent to Wj. The vertices of the edges ej, Wjbk in Qll-1 are neighbors of the vertices of edges ek, vwk in Q°n-1, respectively. Note that the edge wjkwk is incident with v, as v = wjk. See Figure 3 for an illustration. In the rest of the proof we proceed as follows: We find an v-starting Hamiltonian cycle C° = (v, v2,..., v2n-i) of Q°n-1 such that C° contains M \ {ej, ek} U {ek}, the edges of M \ {ej,ek} have the same parity on C° and v2 = wk, v2n-i = wj. Then, the cycle C = Z(C0, k) is a Hamiltonian cycle of Qn containing M. Furthermore, the edges of M \ {ek} = {w1b1,... ,wk-1bk-1,wk+1bk+1,... ,wnbn} have the same parity on C. Then, the paths P1 [w1, b1], . . . , Pk-1 [wk-1, bk-1], Pk+1 [wk+1, bk+1] ,...,Pn[wn, bn] CO CD CD CO u a CD U on C are mutually independent Hamiltonian paths of Qn. Finally, for the differently directed edge ek = wkbk on the cycle C we find a Hamiltonian path Pk [wk ,bk] that is mutually independent with all the other already constructed Hamiltonian paths of Qn. Now, let us find an v-starting Hamiltonian cycle C0 of Qn-1 such that C0 contains M \ {ej, ek} U {ek} and the edges of M \ {ej, ek} have the same parity on C0. Note that ekj = wjkbk is an j-directional edge in Q°n-1 and it is incident with ei for some z E [n] \ {j, k}. We split Q^n-1 along the direction j into subcubes Qn-2 and Qn-2. One of the subcubes Qn°-2 and Qn~2 contains the edges of M' = M \ {ej, ej,ek} vo Jh CD rO a CD a CD CO 00 10 00 w and b on the Hamiltonian cycle C00 of Qn— 2 such that wb / M and b is a black vertex distinct from v. Observe that we can always choose such w and b since n > 4. Note that {wj,bj} fl {wi,bi} = 0. Let P[wk,wl] be the directed path from wk to wl on the Hamiltonian cycle C00, and without loss of generality we may assume that the vertex b follows the vertex w on the path P. Let R1[wk,w],R2[b,wl] be the subpaths of the path P. e CO CO CD CO u Subcase 3.2.1: n = 4. The v-starting Hamiltonian cycle C0 of Q3 is C0 = (v,Ruwj ,bj ,R2,bi,Wi). Jh Subcase 3.2.2: n = 5. Note that we could choose wb among four edges of C00 that are not part of the matching M and are not incident with v. Observe that only one configuration of two pairs of adjacent vertices wjbj and wibi in Q31 up to isomorphism is possible so that there is no Hamiltonian path S[wj, bj] in Q31 — {wi, bi}. Thus, we choose wb such that this configuration is avoided. Then, the desired v-starting Hamiltonian cycle C0 of Q^^ is CD C0 = (v,Ri,S,R2,bi,wi). 00 Subcase 3.2.3: n > 5. We find a Hamiltonian path S[wj,bj] in Q^-2 — {wi,bi} by Proposition 4 and the desired v-starting Hamiltonian cycle C0 of Q^-1 is i—l C0 = (v,Ri,S,R2,bi,wi). O This establishes Subcase 3.2. Finally, it remains to find a Hamiltonian path Pk[wk,bk] of Qn that is mutually independent with already constructed Hamiltonian paths P1,..., Pk-1, Pk+1,... ,Pn of Qn. So, let Pk be the Hamiltonian path of Qn induced by Hamiltonian cycle W(C0, k) of Qn. The CM Hamiltonian path Pr and Pk are independent for every r E [n] \ {k} by Proposition 1, as Pr are Hamiltonian paths induced by Z(C0,k) and bk,wk and wr,br are consecutive pairs of vertices on Z(C0, k). □ CM 4 Independent Hamiltonian cycles in faulty Q? n The following lemma is used as a base of induction in the proof of Theorem 15. Lemma 14. Let F C E(Q4), f = \F\< 2, s E V(Q4). Then, Q4 — F has 4 — f mutually independent s-starting Hamiltonian cycles. | Proof. Let s = 0 be the Startlng vertex We distinguish three cases tegard.ng the number of faulty edges f. Case 1: F = 0. It holds by Theorem 7. Case 2: F = {e}. The proof of this case is straightforward. For a given vertex s = 0 and any faulty edge e, we show that there exist three s-starting mutually independent Hamiltonian cycles. Automorphisms which preserve the vertex s, are called s-preserving. They can be presented as permutations between dimensions. Clearly, s-preserving automorphisms preserve distances to s. Furthermore, note that for every two edges e, g with the same distance to s there exists an s-preserving automorphism that maps e to g. Observe on Figure 4 that the edges svg, v5v13, v4v12, v8v16 are at distance 0, 1, 2, 3 from the vertex s, CD U CU vO $H CD CD a CD CO 00 10 0 o 1 CO ^ CO CO m CD $H CD m u a CD u Figure 4: Three mutually independent s-starting Hamiltonian cycles C1 ,C2, C3 of Q4. Each vertex u of Q4 is associated with a triple (k1, k2, k3) which says that u is the ki-th vertex in the Hamiltonian cycle Ci. respectively. Thus, there exists an s-preserving automorphism of Q4 such that the faulty edge e is mapped to one of the these edges. After applying such automorphism in Q4, the s-starting mutually independent cycles are C1 = (s,v5,v7,v3,v4,vs,v6,v14,v13,v9,vn,v15,v16,v12 ,vW,v2), C2 = (s,v2,v4,v8,v6,v5,v7,v15,v16,v12,vW,v14,v13,v9 ,vn,v3), C3 = (s,v3,vn,vg,v13,v15,v16,v12,v1-,v14, v6, v2, v4, v8, v7, v5). (1) Note that they are all avoiding the edges sv9, v5v13, v4v12, v8v16. For an illustration see Figure 4. Case 3: F = {e1, e2}. First consider the following remark for Q3. There is a Hamiltonian cycle that contains the first edge and avoids the second edge for any two edges of Q3 by Proposition 2. Furthermore, Q3 has two independent Hamiltonian cycles C1 = (s,x1,y1,x2,y3,t,y2 ,x3), C2 = (s,x3,y3,t,y2,x1,y1 ,x2) as on Figure 5 and they are unique up to isomorphism. Notice that the edge y1x2 has the same direction on both cycles. By some s-preserving automorphism of Q3, the edge y1x2 can move to any yixj edge for i,j = 1, 2, 3. Similarly, y3t can move to y1t or y2t by some s-preserving automorphism of Q3. vo $H CD rO a CD a CD CO 00 lO (7,5) (8,2) (2,6) (1,1) Figure 5: Two independent s-starting Hamiltonian cycles Cl = (s,xl,yl,x2,y3,t,y2,x3) and C2 = (s,x3,y3,t,y2,xl,yl,x2) of Q0. Each vertex u of Q0 is associated with a tuple (kl, k2) which says that u is the kl-th vertex in Cl and k2-th vertex in C2. 0 o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO u a CD U We split Q4 along some direction d into Q0 and We assume that s E V(Q0) and vertices of Q0 are denoted as in Figure 5. Now, we distinguish the following cases regarding the position of el and e2: Subcase 3.1: Both el, e2 are incident with s. Then, we may assume that el = sxl and e2 = sx2. In Q3 we find Hamiltonian paths P[sd,xf] and R[x<^,sd}. Observe that Hl = (s,P,Cl \ {s}) and H2 = (C2 \ {sx2},R) are s-starting Hamiltonian cycles of Q4. Furthermore, all except the 9-th vertices of Hl, H2 are in distinct subcubes C0, C\ and the 9-th vertices of Hl, H2 are x<2, x l, respectively. Hence Hl, H2 are independent. For the purpose of clarity in the following cases we denote el = albl and e2 = a2b2. Subcase 3.2: el,e2 E E(Qj). If both el and e2 are incident with sd, then we may assume el = sdxd and e2 = sd^d,. In Ql we find Hamiltonian paths P[sd,xd] R[x<^,sd] which avoids el and e2 by Proposition 2. Then, we can argue as in the previous case that Hl = (s,P,Cl \ {s}) and H2 = (C2 \ {sx2},R) are independent s-starting Hamiltonian cycles of Q4. So, we can assume that e2 is not incident with sd and hence, we can assume that e2 = ydxd or e2 = tdy^. Let H be a Hamiltonian cycle in that contains e2 and avoids el. Then, (Pl, H \ {e2}, P2) and (Rl, H \ {e2},R2) are independent s-starting Hamiltonian cycles in Q4, where P^s,^], P2\bd,x3] are subpaths of Cl and Rl[s,a<2\, R2\b<2,x2] are subpaths of C2. Subcase 3.3: Either el or e2 is incident with s. We can assume el is incident with s. Let d be the direction of el, then e2 can be in Qdd°, Q^1 or it can be of direction d. If e2 is in Q0, then we can assume e2 = ylx2 or e2 = ty3. In we take a Hamiltonian cycle H that contains e2. Then, observe that (Pl, H \ {e2}, P2) and (Rl, H \ {e'd}, R2) are independent s-starting Hamiltonian cycles, where Pl[s,a2], P2[b2,x3] are subpaths of C and Rl[s,a2], R2[b2,x2] are subpaths of C2. If e2 E E(Q^), we take a Hamiltonian cycle H of Ql that avoids e2 and contains an edge (ylx2)d, or (ty3)d. Then, (Pl,H \ {(ty3)d},P2) and (Rl,H \ {(ty3)d}, R2) are independent s-starting Hamiltonian cycles, where Pi[s,t], P2[y3,x3] are subpaths of C1 and Rl[s,t], R2[y3,x2] are subpaths of C2. Finally, if e2 is of direction d, then ylx2 or ty3 is not incident with e2. Let us assume ty3 is not incident with e2. We take a Hamiltonian cycle H that contains (ty3)d in Then, (Pi, H \ {(ty3)d}, P2) and (Rl,H \ {(ty3)d},R2) are independent s-starting Hamiltonian cycles, where Pl[s,t], P2[y3,x3] are subpaths of Cl, Rl[s,t] and R2[y3,x2] are subpaths of C2. Subcase 3.4: Finally, excluding the previous cases, the direction d keeps el in Q3 and e2 in Ql As el is not incident with s, we can assume el = ylx2 or el = ty3. Again, we take a Hamiltonian cycle H in Q\ that contains ef. We may assume H avoids e2 unless ef = e2. Now (Pl, H\{el}, P2) and (Rl, H\{ed}, R2) are independent s-starting Hamiltonian cycles, where Pl[s,al], P2[bl,x3] are subpaths of Cl and Rl[s,al], R2[bl,x2] are subpaths of C2. 00 □ u CD a CD lO o CSI I CO The following theorem improves Theorem 10 by one additional Hamiltonian cycle. For simplicity, let us denote 0 = {0}n and 1 = {1}n in Qn. Theorem 15. Let F C E(Qn), n > 4, f = \F\ < n — 2, and s e V(Qn). Then, Qn — F has n — f mutually independent s-starting Hamiltonian cycles. Proof. If Qn has no faulty edges, i.e. f = 0, then Qn has n mutually independent s-starting Hamiltonian cycles by Theorem 7. So, we assume f > 1. We proceed by induction on n. For n = 4 the statement holds by Lemma 14. Let us assume that the statement holds for n — 1, and we will prove it for n > 5. By symmetry, we may assume s = 0 e V(Qn). Furthermore, let DF = {d e [n]; 3vvd e F} be the set of 00 directions of faulty edges in Qn. In the following we need one additional definition. Assume that Cl,C2,..., Cn-f are mutually independent Vi,^starting Hamiltonian cycles in Qm for n — f < m < n and Ci = (vi,l,Vi,2,... ,Vi,2m). Then, for u = (ul,u2,... ,Un-m) e V(Qn-m) let Cu, C%,..., Cl_f be the Hamiltonian cycles in Qm'd''dn-m);u, where dl < ••• < dn-m CO and dl,..., dn_m e DF. Let us denote SU = {(vhk,u) e V(Qm); i e [n - f]}; that is, SU is the set of k-th vertices of CU,CU,..., CU-f. First, we consider the case of one faulty edge. See Figure 6(a) for an illustration. We split Qn along the direction d of the faulty edge into subcubes Q^ijQ^i. By induction, there are n — 1 mutually independent s-starting Hamiltonian cycles C0,C2>... Cn-i in Q°n-l — F. As 2n-1 — 2 — 2(n — 1) > 0 for n > 5, we can find an integer 1 < k < 2n-1 such CD that none of the vertices of Sk U S,0+l is incident with the faulty edge. We map the vertices of S0, S0+l along the direction d into Qn_l and obtain Si, Sl+l; which are sets of distinct n — 1 pairs of adjacent vertices vdk, vdi+l in Qn_l. In Qn_l there are no faulty edges, so by Theorem 13, in Qn_l — F there are n — 1 mutually independent Hamiltonian paths Ul[vl i Mi i+l],U2 [vi i ,vdt i+lL . . . , Un_l[vdn_l 11 yn_l i i+l]. vo $H CD rO CD a CD CO 00 lO Qr Qr Qr Figure 6: The construction of a set of s-starting mutually independent Hamiltonian cycles in Qn with: (a) one faulty edge, (b) at least two faulty edges of the same direction d, (c) a faulty edge of direction d and at least one faulty edge in Q^^- 0 o CM 1 CM 00 CM CM £ CO CO CO CD $H CD CO u a CD U Then, for every i E [n — f ], Ci = (Ti, Ui, Ri) is an s-starting Hamiltonian cycle in Qn where Ti[s,vi,k},Ri[vi>k+1 ,vik2n-i] are subpaths of the cycle C0. Moreover, the cycles C1, C2,..., Cn-1 are mutually independent. Next, if there are two or more faulty edges (i.e. f > 2), we distinguish three cases. Case 1: F is not rigid. Then, there exists a direction d E DF containing at least two faulty edges. We split Qn along the direction d into Qn_ 1; Qn~ 1. Let f2 be the number of faulty edges of direction d, and let fo, f1 be the number of faulty edges in Qn_ 1; Qn_ 1; respectively; so f0 + f 1 + f2 = f. By induction, we can find n — 1 — f0 mutually independent Hamiltonian cycles C0, C0,..., C'0_1_fo in Q0n-1 — F. We take the first n — f cycles C0, C0,..., C^f. We choose k such that 1 < k < 2n-1 and none of the vertices of S0, S°+1 is incident with any faulty edge of direction d. Such k exists as 2n-1 — 2 — 2f2(n — f ) > 0 for all n > 5. We map the vertices of S0, S°+1 along the direction d into Qn_ 1 and we obtain SS1 ^fc+u which are sets of n — f pairs of adjacent vertices v2k, v2k+1 in Qn_ 1. Since n — f < n — 2 — f1 there exist n — f mutually independent Hamiltonian paths U1[v{k ^t^i ^Kk, vik k+l], . . . , Un-f [vdn_fk ,vdn_f,k+1] of QL -1 — F by Lemma 9. Then, for every i E [n — f ], Ci = (Ti, Ui, Ri) is an s-starting Hamiltonian cycle in Qn — F where Ti[s,vikk],Ri[vikk+1,vi,2n-i] are the subpaths of the cycle C0. Moreover, the cycles C1, C2,..., Cn-f are mutually independent. See Figure 6(b) for an illustration. Case 2: F is rigid and there exists a direction d E DF such that the subcube Q2— contains at least one faulty edge. We split Qn along the direction d into Qn_ 1; Qn_ 1. Let f0, f1 be CD CO u the number of faulty edges in Qn-i, Qn_i, respectively; so 0 < f0 < f and f0 + fi + 1 = f. We proceed similarly as in Case 1. By induction, there are n — 1 — f0 mutually independent Hamiltonian cycles C°, C°,..., C0-i-f0 in Q°n_i — F. We take the first n — f cycles C°,C°,... ,C°n_f and choose k such that 1 < k < 2n-i and none of the vertices of S°k U S°+i is incident with the faulty edge of direction d. We always find such k as 2n-i — 2 — 2(n — f) > 0 for n > 5. We map the vertices of S°+i along the direction d into Q1n-i and we obtain Si, Sl+i; which are sets of n — f pairs of adjacent vertices vfkk, vd,k+i in Q^n-i. Since n — f < n — 2 — fi, we can find n — f mutually independent Hamiltonian paths CD Ui[v{ k ,v{ k+i], U2[vlk k+l],. . . , Un-f [vdn-f, k ,vdn-f, k+i] of Qn-i — F by Lemma 9. Then, for every i E [n — f ], lO Ci = (Ti,Ui,Ri), is an s-starting Hamiltonian cycle in Qn — F where Ti[s,vi,k], Ri[vi,k+i,vi,2n-i] are subpaths of the cycle C0. Moreover, the cycles Ci,C2,...,Cn-f are mutually independent. See Figure 6(c) for an illustration. Case 3: F is rigid and for every d E Dp, the subcube Qdrl_i has no faulty edge. We can consider Qn as a Cartesian product Qn = Qn_f+i □ Qf-i such that the coordinates of Qf-i are obtained by projection of the coordinates of Qn on Dp \ {z} for some z E Dp. Let ez denote the faulty edge of direction z. Let us define Zp = (di,d2,... ,df-i) for di,..., df-i E Dp \ {z} and di < • • • < df-i. For the purpose of clarity let us denote r = 2f-i and q = 2n-f+i. Furthermore, let H = (ui,u2,... ,ur) be an arbitrary Hamiltonian cycle of Qf-i such that ui = 0. Let tj denote the direction of the edge UjUj+i. Recall that Q^-'f+i are subcubes of Qn for every j E [r] and s E V(Q^f+i)• Since there exists no direction d E Dp such that Qdrl—i has a faulty edge, one faulty edge is in Q^n_f+i and all CO the others are incident with precisely one vertex from Qn_f+i. By Theorem 7, we can find CO n — f mutually independent s-starting Hamiltonian cycles C0,C0,..., C0_f in Q°n_f+i. Let C0 = (vi , i ,vi, 2,.. .,vi, q). Regarding the number of faulty edges, we distinguish two cases. Subcase 3.1: f > 3. See Figure 7 for an illustration of case, when f = 3. Since f > 3, the vertex u2 is never antipodal to the vertex ui = 0 in Qf_i, i.e. u2 = 1. Hence Qn_f+i has no faulty edge and there is no faulty edge of direction ti incident with a vertex from QUI Qn_f +i- We choose k such that 1 < k < q and map the vertices S0, S^ along the direction ti into Qn_f+i. We obtain vertices SU2, S'U+i which are sets of n — f distinct pairs of adjacent vertices v\\, v\ 1k+i in Qn_f+i. The subcube Qn_f+i is of dimension n — f + 1 and has a set of n — f edges N = {vii1kvii1k+i; i E [n — f]}. We extend N into the perfect matching M of QUn_f+i and find a Hamiltonian cycle G2 = (wi,w2,... ,wq) containing the edges of M by Theorem 5. Note that the edges of N have the same parity on G2 as they are included in the perfect matching M. CD U CU vo Jh CD CD a CD CO 00 lO 0 o 1 CO ^ CO CO CD Jh CD u a CD u Qu4 n-2 Qn-2 n-2 Qu2 n-2 Figure 7: The construction of n — 3 mutually independent Hamiltonian cycles in Qn for n > 5, when the faulty edges are rigid and for every direction, d G DF, the subcube Q^^-i has no faulty edge (The example of Subcase 3.1). Now, we choose an edge a2b2 on G2 such that a2b2 is not incident with the faulty edge of direction t2 (if such faulty edge exists) and distinct from N. Note that we can always choose such a2b2 as n — f + 2 < 2n for f > 3 and n > 5. Let us assume that a2b2 and v^kVi1k+1 have different parity on G2. We map a2 and b2 along the direction t2 into Qn—f+1-By Proposition 2 we find a Hamiltonian path G3 [a|2 ,b2 ] in Qn—f+1 which avoids ez (if ez G E (Qn—f+1))- We proceed similarly for every j = 3, 4,...,r. We choose consecutive vertices aj, bj on Gj such that aj, bj, aj—l, bj'-l are distinct. We map aj and bj along the direction tj into Qun--+1+1 and by Proposition 2 we find a Hamiltonian path Gj+1[aj'-1, bj'-l] in Qun--1+1 that avoids ez (if ez G E(Qn-~f+1)). Then, for all i G [n — f] _ i T)i T)i T) T) Q rji rji rpi rpi\ Ci = (R^ R2, R3, . . . , Rr-1, S, Tr-1, ■ ■ ■ , T3, T2, T 1) are mutually independent Hamiltonian cycles, where R\[s,vikk], Ti[viik+1,viq] are subpaths of C0, R22[vtiLk,a2], T2i[b2,vtiik+1 ] are subpaths of G2, S[atrr-1 ,btrr-1 ] is a subpath of Gr and Rj[a/_i, aj], Tj [bj, b—l] are subpaths of Gj for every j = 3, 4, Subcase 3.2: hypercube Qn. , r — 1. f = 2. We further distinguish this case regarding the dimension of the Subcase 3.2.1: n > 6. Let d1, d2 be the directions of faulty edges ei, e2, respectively and let us denote q = 2n_2. We split Qn along d1 and d2 into Q^^2^00, Qn 2 , vO $H CD CD a CD CO 00 10 0 £ o 1 CO ^ CO CO Q10 Qn—2 Q00 Qn—2 Qn— 2 Q01 Qn—2 Figure 8: The construction of n — 2 mutually independent Hamiltonian cycles in Qn for n > 6, when the faulty edges f1, f2 are rigid and for every direction, d E {d1,d2}, the subcube Qdr;—1 has no faulty edge. Q(di,d2)-,11 Qn-2 , Q(di ,d2);01 Qn-2 • We find n — 2 mutually independent s-starting Hamiltonian cycles uiq) in Qn°-2 by Theorem 7. See Figure 8 for an illustration. We C—0 = (ui1,uh2,..., choose k such that 1 < k < q and map the vertices of S—0, S—+1 along d2 into Qn_2. We obtain S-1, Sk1^; which are sets of n — 2 pairs of adjacent vertices ud'k, ud'k+1 in Q°ni_2. We can find n — 2 mutually independent Hamiltonian paths pi[ul% >ul%+l], • • • , Pn-2[u„—2,k ,Un-2,k+l\ d2 n m CD Jh CD CO u a CD U of Q0n-2 by Theorem 13. Then, C?1 = P% U {udku^} )• We choose l such that 1 < l < q i,q every i E [n — 2]. Let us denote C—1 = (vi>1,vi>2, and none of the vertices S—1 U S—+1 is incident with the faulty edge e1. We can always find such l as 2n_2 — 1 — 2(n — 2) > 0 for n > 6. We map the vertices of S—1, SS—+1 along d1 into Qn_2 and obtain S11, S+ ; which are sets of n — 2 pairs of adjacent vertices vd], Qln-2. We can find n — 2 mutually independent Hamiltonian paths di Ji,l+1 Ri[vd ,di vdi i, vi,i+i ^•••,Rn-2[vÎ-2il Vn-2,1+1 ] d of Qn- 2 by Theorem 13. The^ Ci = Ri U {vdivdi+i} is a Hamiltonian cycle of Qn_2 for every i E [n — 2]. Let us denote C11 = (wi>1,wi>2,... ,wiq). We choose t such that 1 < t < q and and none of the vertices S1 U S^ is incident with the faulty edge e2. We can always find such t as 2n 2 — 1 — 2(n — 2) > 0 for n > 6. We map the vertices of Stn, S^ along d2 into Q— and obtain St10, St+h; which are sets of n — 2 pairs of adjacent vertices wdt, vO Wdt+1 in Qn°-2- We can find n — 2 mutually independent Hamiltonian paths U CD CD O i CD m u Vl[wt2t, <2i+1], • • • , Vn-2[wdn-2p Wdn-2,t+1] of Qn0- 2 by Theorem 13. Then, for every i G [n — 2], Ci — (Ti, Pi,i,Rii, Vi,Ri,2, Pi,2, Ui) CD is an s-starting Hamiltonian cycle in Qn — {e1,e2} where Ti[s,ui,k], Ui[ui,k+1,ui,q] are sub-paths of C00, Pi,i[vi,i,vi,i], Pi,2[vi,i+i,Vi,q] are subpaths of Pi and Ri,i[wi,i, Wi;i], Ri,2[wi,t+i,wi,q] are subpaths of Ri. Moreover, the cycles Ci, C2,..., Cn-2 are mutually independent. Subcase 3.2.2: n — 5. Let us denote F — {ei,e2}. We split Q5 along the direction d of the faulty edge ei. Then, Q4 contains the vertex s and Q4 contains e2. In Q4 we choose three mutually independent s-starting Hamiltonian cycles Ci,C2,C3 defined by (1), see Figure 4. From independent directed edges v4v8, vi5vi6, vi2vi0 of Ci,C2,C3, we choose the edge e — ab such that e is not incident with ei. In Q4 we find a hamiltonian path P[ad, bd] which avoids e2. We obtain three mutually independent s-starting fault-free Hamiltonian cycles o Ci — (Ri,P,Pi), C2 =(R2,P,P2), C3 = (R3, P, P3), CM where R1 [s, a], P1 [b, v2] are subpaths of C1, R2[s, a], P2[b, v3] are subpaths of C2 and R3[s, a], P3[b,v5] are subpaths of C3. □ 5 Conclusion In this paper we study the problem of mutually independent Hamiltonian paths and s-starting Hamiltonian cycles of n-dimensional hypercube Qn. We prove that there are k < 2n-1 mutually independent Hamiltonian paths P1[wv1,b1], P2[wv2,b2],..., Pk[wk,bk] for a matching M = {w1b1,w2b2,... ,wkbk} C E(Qn) if M is extendable to a perfect matching. We prove that there are n mutually independent Hamiltonian paths Pj[wj,bj] for any matching M = {w1b1,w2b2,... ,wnbn} C E(Qn) in Qn which improves previously known result by one additional Hamiltonian path. We also prove that there are n — f mutually independent s-starting Hamiltonian cycles in Qn — F, where F is a set of f < n — 2 arbitrary faulty edges and s is an arbitrary vertex. This improves previously known result by one additional s-starting Hamiltonian cycle. Moreover, it is the optimal result as faulty edges may be all incident with the vertex s. vo $H CD rO CD Oh CD CO 00 10 0 £ o CM 1 CM CO CM CM £ CO CO References [1] J. Fink, Perfect Matchings Extend to Hamilton Cycles in Hypercubes, J. Com-bin. Theory Ser. B 97 (2007) 1074-1076. [2] I. Havel, On Hamiltonian circuits and spanning trees of hypercube, Cas. Pest. Mat. 109 (1984) 135-192. [3] S. Y. Hsieh, Y. F. Weng, Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults, Theor. Comp. Sys. 45 (2009) 407-425. [4] S. Y. Hsieh, P. Y. Yu, Faulty-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges, J. Comb. Optim. 13 (2007) 153-162. [5] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Com-bin. Appl. 16 (1996) 87-91. [6] T. Z. Kueng, C. K. Lin, T. Liang, J. J.M. Tan, L. H. Hsu, A Note on Faulty-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges, J. Comb. Optim. 17 (2009) 312-322. [7] M. Lewinter, W. Widulski, Hyper-Hamilton laceable and caterpillar-spannable product graphs, Computer Math. Applic. 34 (1997) 99-104. [8] N. B. Limaye, D. G. Sarvate, On r-Extendability of the Hypercube Qn, Math. Bohemica 122 (1997) 249-255. [9] Y. K. Shih, J. J. M. Tan, L. H. Hsu, Mutually independent bipanconnected property of hypercube, Appl. Math. Comput. 217 (2010) 4017-4023. [10] C. M. Sun, C. K. Lin, H. M. Huang, L. H. Hsu, Mutually Independent Hamiltonian Cycles in Hypercubes, Proc. 8th Sympos. on Parallel Architectures, Algorithms and Networks (2005). [11] C. H. Tsai, J. J. M. Tan, T. Liang, L. H. Hsu, Fault-tolerant hamiltonian laceability of hypercubes, Info. Proc. Letters 83 (2002) 301-306. m CD $H CD m u a CD U