Let Qn,k (n 〉 3, 1 〈 k ≤ n - 1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty ve...Let Qn,k (n 〉 3, 1 〈 k ≤ n - 1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n - 2fv - 1 (respectively, 2n - 2fv - 2) can be embedded on Qn,k with fv + f≤ n- 1 when dQn,k (u, v) is odd (respectively, dQ,~,k (u, v) is even). Secondly, an Q,,k is (n - 2) edgefault-free hyper Hamiltonianaceable when n ( 3) and k have the same parity. Lastly, a fault-free cycle of length at least 2n - 2fv can be embedded on Qn,k with f~ 〈 n - 1 and fv+f≤2n-4.展开更多
基金supported by NSFC (11071096, 11171129)NSF of Hubei Province, China (T201103)
文摘Let Qn,k (n 〉 3, 1 〈 k ≤ n - 1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n - 2fv - 1 (respectively, 2n - 2fv - 2) can be embedded on Qn,k with fv + f≤ n- 1 when dQn,k (u, v) is odd (respectively, dQ,~,k (u, v) is even). Secondly, an Q,,k is (n - 2) edgefault-free hyper Hamiltonianaceable when n ( 3) and k have the same parity. Lastly, a fault-free cycle of length at least 2n - 2fv can be embedded on Qn,k with f~ 〈 n - 1 and fv+f≤2n-4.