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.展开更多
In this paper, a t/(t+1)-diagnosable system is studied, which can locate a set S with |S|≤t+1 containing all faulty units only if the system has at most t faulty units. On the basis of the characterization of the t/(...In this paper, a t/(t+1)-diagnosable system is studied, which can locate a set S with |S|≤t+1 containing all faulty units only if the system has at most t faulty units. On the basis of the characterization of the t/(t+1)-diagnosable system, a necessary and sufficient condition is presented to judge whether a system is t/(t+1)-diagnosable. Meanwhile, this paper exposes some new and important properties of the t/(t+1)-diagnosable system to present the t/(t+1)-diagnosability of some networks. Furthermore, the following results for the t/(t+1)-diagnosability of some special networks are obtained: a hypercube network of n -dimensions is (3n-5)/(3n-4)-diagnosable, a star network of n -dimensions is (3n-5)/(3n-4)-diagnosable (n≥5) and a 2D-mesh (3D-mesh) with n 2(n 3) units is 8/9-diagnosable (11/12-diagnosable). This paper shows that in general, the t/(t+1)-diagnosability of a system is not only larger than its t/t -diagnosability , but also its classic diagnosability, specially the t/(t+1)-diagnosability of the hypercube network of n -dimensions is about 3 times as large as its classic t -diagnosability and about 1.5 times as large as its t/t -diagnosability.展开更多
基金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.
基金supported by Youth Project of National Natural Science Foundation of China“The discrete isoperimetric problem of graphs and the study of weierstrass type functions with extremely related conditional connectivity”(12101528)。
基金Supported by the National Natural Science Foundation of China(No.61862003,61761006)the Natural Science Foundation of Guangxi of China(No.2018GXNSFDA281052)
文摘In this paper, a t/(t+1)-diagnosable system is studied, which can locate a set S with |S|≤t+1 containing all faulty units only if the system has at most t faulty units. On the basis of the characterization of the t/(t+1)-diagnosable system, a necessary and sufficient condition is presented to judge whether a system is t/(t+1)-diagnosable. Meanwhile, this paper exposes some new and important properties of the t/(t+1)-diagnosable system to present the t/(t+1)-diagnosability of some networks. Furthermore, the following results for the t/(t+1)-diagnosability of some special networks are obtained: a hypercube network of n -dimensions is (3n-5)/(3n-4)-diagnosable, a star network of n -dimensions is (3n-5)/(3n-4)-diagnosable (n≥5) and a 2D-mesh (3D-mesh) with n 2(n 3) units is 8/9-diagnosable (11/12-diagnosable). This paper shows that in general, the t/(t+1)-diagnosability of a system is not only larger than its t/t -diagnosability , but also its classic diagnosability, specially the t/(t+1)-diagnosability of the hypercube network of n -dimensions is about 3 times as large as its classic t -diagnosability and about 1.5 times as large as its t/t -diagnosability.
