The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the gue...The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the vip graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where ｜Fv｜ is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.展开更多
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 fau...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 Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv 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^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.展开更多
In this paper,we focus on the vertex-fault-tolerant cycles embedding on enhanced hypercube,which is an attractive variant of hypercube and is obtained by adding some complementary edges from hypercube.Let Fv be the se...In this paper,we focus on the vertex-fault-tolerant cycles embedding on enhanced hypercube,which is an attractive variant of hypercube and is obtained by adding some complementary edges from hypercube.Let Fv be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k（1 ≤ k≤n- 1）.When ｜F_v｜ = 2,we showed that Qn,k-Fv contains a fault-free cycle of every even length from 4 to 2^n- 4 where n（n ≥ 3） and fc have the same parity;and contains a fault-free cycle of every even length from 4 to 2^n- 4,simultaneously,contains a cycle of every odd length from n — fc ＋ 2 to 2^n-3 where n（≥ 3） and fc have the different parity.Furthermore,when ｜Fv｜= fv ≤ n- 2,we proof that there exists the longest fault-free cycle,which is of even length 2^n- 2fv whether n（n 〉 3） and fe have the same parity or not;and there exists the longest fault-free cycle,which is of odd length 2^n-2fv- 1 in Qn,k — Fv where n（≥ 3） and fc have the different parity.展开更多
基金Supported by the National Natural Science Foundation of China(11071022)the Key Project of Hubei Department of Education(D20092207)
文摘The generalized conditional fault-tolerant embedding is investigated, in which the n-dimensional folded hypercube networks （denoted by FQn） acts as the host graph, and the longest fault-free cycle represents the vip graph. Under the conditions looser than that of previous works, it is shown that FQn has a cycle with length at least 2n -21F, I when the number of faulty vertices and non-critical edges is at most 2n-4; where ｜Fv｜ is the number of faulty vertices. It provides further theoretical evidence for the fact that FQn has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.
基金supported by NSFC(11071096 and 11171129)Hubei Province,China(T201103)
文摘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 Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv 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^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.
基金Supported in part by the National Natural Science Foundation of China under Grant No.11371162 and 11171129National Natural Science Foundation of Hubei Province No.T201103
文摘In this paper,we focus on the vertex-fault-tolerant cycles embedding on enhanced hypercube,which is an attractive variant of hypercube and is obtained by adding some complementary edges from hypercube.Let Fv be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k（1 ≤ k≤n- 1）.When ｜F_v｜ = 2,we showed that Qn,k-Fv contains a fault-free cycle of every even length from 4 to 2^n- 4 where n（n ≥ 3） and fc have the same parity;and contains a fault-free cycle of every even length from 4 to 2^n- 4,simultaneously,contains a cycle of every odd length from n — fc ＋ 2 to 2^n-3 where n（≥ 3） and fc have the different parity.Furthermore,when ｜Fv｜= fv ≤ n- 2,we proof that there exists the longest fault-free cycle,which is of even length 2^n- 2fv whether n（n 〉 3） and fe have the same parity or not;and there exists the longest fault-free cycle,which is of odd length 2^n-2fv- 1 in Qn,k — Fv where n（≥ 3） and fc have the different parity.
