Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whos...Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h; and the h-extra connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, if any, whose deletion disconnects G and every remaining component has order more than h. This paper shows that for the hypercube Qn and the folded hypercube FQn, κ1（Qn）=κ（1）（Qn）=2n-2 for n≥3, κ2（Qn）=3n-5 for n≥4, κ1（FQn）=κ（1）（FQn）=2n for n≥4 and κ（2）（FQn）=4n-4 for n≥8.展开更多
System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem...System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem of fault identification in an unstructured graph has been proved to be NP-hard （non-deterministic polynomial-time hard）. In this paper, we adopt the PMC diagnostic model （first proposed by Preparata, Metze, and Chien） as the foundation of point-to-point probing technology, and a system contains only restricted-faults if every of its fault-free units has at least one fault-free neighbor. Under this condition we propose an efficient method of identifying restricted-faults in the folded hypercube, which is a promising alternative to the popular hypercube topology.展开更多
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 guest 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.展开更多
For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimensi...For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimension cube＇s, the minimum k required to represent G is called the cubicity of G. In this paper, a special graph .called unit-interval graph. IG[X, Y] is given, then 2n such graphs which have the same vertices as V（FQn） are constructed, where FQ, is the n-dimension folded hypercube. Thanks to the specia] structure of IG[X, Y], the result that cubicity（FQn）≤ 2n is proved.展开更多
文摘Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h; and the h-extra connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, if any, whose deletion disconnects G and every remaining component has order more than h. This paper shows that for the hypercube Qn and the folded hypercube FQn, κ1（Qn）=κ（1）（Qn）=2n-2 for n≥3, κ2（Qn）=3n-5 for n≥4, κ1（FQn）=κ（1）（FQn）=2n for n≥4 and κ（2）（FQn）=4n-4 for n≥8.
基金supported in part by the NSC under Grand No.NSC102-2221-E-468-018
文摘System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem of fault identification in an unstructured graph has been proved to be NP-hard （non-deterministic polynomial-time hard）. In this paper, we adopt the PMC diagnostic model （first proposed by Preparata, Metze, and Chien） as the foundation of point-to-point probing technology, and a system contains only restricted-faults if every of its fault-free units has at least one fault-free neighbor. Under this condition we propose an efficient method of identifying restricted-faults in the folded hypercube, which is a promising alternative to the popular hypercube topology.
基金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 guest 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.
文摘For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimension cube＇s, the minimum k required to represent G is called the cubicity of G. In this paper, a special graph .called unit-interval graph. IG[X, Y] is given, then 2n such graphs which have the same vertices as V（FQn） are constructed, where FQ, is the n-dimension folded hypercube. Thanks to the specia] structure of IG[X, Y], the result that cubicity（FQn）≤ 2n is proved.
