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.展开更多
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.展开更多
Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining ...Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining component with minimum degree δ no less than m. This study shows that λ;(Q;) = 2 n,λ;(Q;) = 4 n-4（2 ≤ k ≤ n-1, n ≥ 3） for n-dimensional enhanced hypercube Q;. Meanwhile, another easy proof about λ;（Q;） = 4 n-8, for n ≥ 3 is proposed. The results of enhanced hypercube include the cases of folded hypercube.展开更多
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.展开更多
Efficiency and reliable routing can be achieved by using internally nodedisjoint paths （disjoint path for short） because they can be used to avoid congestion, accelerate the transmission rate, and provide alternativ...Efficiency and reliable routing can be achieved by using internally nodedisjoint paths （disjoint path for short） because they can be used to avoid congestion, accelerate the transmission rate, and provide alternative transmission routes. It is well known that there are n disjoint paths connecting any two nodes in an n-dimensional hypercube （n-cube for short）. In order to enhance the performance and reliability, several variants of n-cube networks have been proposed. The enhanced hypercube networks （denoted by Qn,k） is one of these variation. In this paper, its structural natures are obtained in detail and its properties and performance have been analyzed. The minimum transmission delay of enhanced hypercube Qn,k has been proved equal to k ＋q┌n-k＋1/2┐.The one-to-one routing process is also concerned, this paper also proves that＇ thereexists n ＋ 1 internally-disjoint paths between any two distinct nodes in Qn,k for k = 2. It follows that its connectivity and edge-connectivity are n ＋ 1.展开更多
基金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.
基金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.
文摘Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining component with minimum degree δ no less than m. This study shows that λ;(Q;) = 2 n,λ;(Q;) = 4 n-4（2 ≤ k ≤ n-1, n ≥ 3） for n-dimensional enhanced hypercube Q;. Meanwhile, another easy proof about λ;（Q;） = 4 n-8, for n ≥ 3 is proposed. The results of enhanced hypercube include the cases of folded hypercube.
基金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.
基金This project is supported by National Natural Science Foundation of China （10671081） the Science Foundation of Hubei Province （2006AA412C27）
文摘Efficiency and reliable routing can be achieved by using internally nodedisjoint paths （disjoint path for short） because they can be used to avoid congestion, accelerate the transmission rate, and provide alternative transmission routes. It is well known that there are n disjoint paths connecting any two nodes in an n-dimensional hypercube （n-cube for short）. In order to enhance the performance and reliability, several variants of n-cube networks have been proposed. The enhanced hypercube networks （denoted by Qn,k） is one of these variation. In this paper, its structural natures are obtained in detail and its properties and performance have been analyzed. The minimum transmission delay of enhanced hypercube Qn,k has been proved equal to k ＋q┌n-k＋1/2┐.The one-to-one routing process is also concerned, this paper also proves that＇ thereexists n ＋ 1 internally-disjoint paths between any two distinct nodes in Qn,k for k = 2. It follows that its connectivity and edge-connectivity are n ＋ 1.
