بانک مقالات تخصصی ریاضی

Code: 20137

Vertex-Fault-Tolerant Cycles Embedding on Enhanced Hypercube Networks

Yanjuan Zhang, Hongmei Liu, Min Liu

Abstracts

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let F_v be the set of faulty vertices in the n-dimensional enhanced hypercube Q_n,k (n ≥ 3, 1 ≤ k ≤ n − 1). When |F_v| = 2, we showed that Q_n,k − F_v contains a fault-free cycle of every even length from 4 to 2ⁿ – 4 where n (n ≥ 3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2ⁿ − 4, simultaneously, contains a cycle of every odd length from n − k + 2 to 2ⁿ − 3 where n (≥ 3) and k have the different parity. Furthermore, when |F_v| = f_v ≤ n − 2, we prove that there exists the longest fault-free cycle, which is of even length 2ⁿ − 2f_v whether n (n ≥ 3) and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2ⁿ − 2f_v + 1 in Q_n,k − F_v where n (≥ 3) and k have the different parity