It is well-known that connectivity is closely related to diagnosability.If the relationships be-tween them can be established,many kinds of diagnosability will be determined directly.So far,some notable relationships ...It is well-known that connectivity is closely related to diagnosability.If the relationships be-tween them can be established,many kinds of diagnosability will be determined directly.So far,some notable relationships between connectivity and diagnosability had been revealed.This paper in-tends to find out the relationship between extra connectivity and t/k-diagnosability under the PMC(Preparata,Metze,and Chien)model.Then,applying this relationship,the t/k-diagnosability of bijective connection(BC)networks are determined conveniently.展开更多
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.展开更多
基金Supported by the National Natural Science Foundation of China(No.62262032,61862035,61562046)National Natural Science Foundation of Jiangxi Province(No.20202BABL202042)the Science and Technology Project of Jiangxi Provincial Education Department(No.GJJ2201604,GJJ201033,GJJ190560).
文摘It is well-known that connectivity is closely related to diagnosability.If the relationships be-tween them can be established,many kinds of diagnosability will be determined directly.So far,some notable relationships between connectivity and diagnosability had been revealed.This paper in-tends to find out the relationship between extra connectivity and t/k-diagnosability under the PMC(Preparata,Metze,and Chien)model.Then,applying this relationship,the t/k-diagnosability of bijective connection(BC)networks are determined conveniently.
文摘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.
