In recent years, due to the continuous expansion of the scale of multi-processor systems, processor fault diagnosis has become increasingly important in measuring system reliability. Diagnosability of many well-known multiprocessor systems has been extensively studied. Conditional diagnosability is a new system diagnostic measure that inserts an additional condition that all neighbors (adjacent nodes) of any node in the system cannot all fail at the same time. In this report, we evaluate the conditional diagnosability for enhanced hypercubes under the PMC model. We first give several properties about hypercubes and enhanced hypercubes, and then based on these properties, the conditional diagnosability of an$(n,k)$-enhanced hypercube$Q_{n,k}$is proved to be$4n-7$for$n\ge 5$and$k=3$, and to be$4n-3$for$n\ge 6$and$5\le k\le n$.

Fault diagnosis of processors has played an essential role when evaluating the reliability of multiprocessor systems. In many novel multiprocessor systems, their diagnosability has been extensively explored. Conditional diagnosability is a useful measure for evaluating diagnosability by adding a further condition that all neighbors of every node in the system do not fail at the same time. In this paper, we study the conditional diagnosability of n-dimensional alternating group networks ANn under the PMC model, and obtain the results tc(AN4) = 5, and tc(ANn) = 6n - 17 for n > 5. In addition, for the isomorphism property between ANnand Sn,kwith k = n-2, namely (n, n - 2)-star graphs Sn,n-2, the above results can be extended to Sn,n-2, and we have tc(S4,2) = 5 and tc(Sn,n-2) = 6n - 17 for n > 5. It is worth noting that the conditional diagnosability is about six times the degree of ANn andSn,n-2, which is very different from general networks with a multiple of four.

Fault diagnosis has played a major role in measuring the reliability of multiprocessor systems. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel property of measuring diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of (n, k)-star graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of (n, k)-star graphs under the PMC model, and show that it is 1) ⌈2/n⌉ -1 for n ≥ 4 and k = 1, and 2) n + 3k - 6 for 2 ≤ k ≤ n-3.

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n-11 for n ≥ 4 except for the n -dimensional star graph for which it has been shown to be 8 n -21 for n ≥ 5 (refer to Chang and Hsieh [2014]).

The (n,k)-star graph, denoted by Sn,k, is an enhanced version of n-dimensional star graphs Sn, that has better scalability than Sn, and possesses several good properties, compared with hypercubes. Diagnosis has been one of the most important issues for maintaining multiprocessor-system reliability. Conditional diagnosability, which is more general than classical diagnosability, measures the multiprocessor-system diagnosability under the assumption that all neighbors of any processor in the system cannot fail simultaneously. In this paper, we investigate the conditional diagnosability of Sn,kfor ( n ≥ 3 and k=1) and ( n ≥ 4 and 2 ≤ k ≤ n) under the comparison diagnosis model.

Given a graph${\mbi{G}}$and a non-negative integer${{g}}$, the${{g}}$-extra connectivity (resp.${{g}}$-extra edge connectivity) of${\mbi{G}}$is the minimum cardinality of a set of vertices (resp. edges) in${\mbi{G}}$, if it exists, whose deletion disconnects${\mbi{G}}$and leaves each remaining component with more than${{g}}$vertices. This study shows that the 3-extra connectivity (resp. 3-extra edge connectivity) of an${\mbi{n}}$-dimensional folded hypercube is${4}{{n}} - {5}$for${{n}} \geq {6}$(resp.${4}{{n}} - {4}$for${{n}} \geq {5}$). This study also provides an upper bound for the${{g}}$-extra connectivity on folded hypercubes for${{g}} \geq {6}$.

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system; the diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability. It includes a condition whereby any fault set cannot contain all the neighbors of any node in a system. In this paper, the conditional diagnosability of star graphs by using the PMC model is evaluated. Several new structural properties of star graphs are derived. Based on these properties, the conditional diagnosability of an$n$-dimensional star graph is determined to be$8n-21$for$n\geq 5$.

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a novel measure of diagnosability by adding an additional condition that any faulty set cannot contain all the neighbors of any node in a system. In this paper, we evaluate the conditional diagnosability for augmented cubes under the PMC model. We show that the conditional diagnosability of an n-dimensional augmented cube is 8n - 27 for n≥5.

Processor fault diagnosis plays an important role in measuring the reliability of multiprocessor systems and the diagnosis of many well-known interconnection networks. The conditional diagnosability, which is more general than the classical diagnosability, is to measure the diagnosability of a multiprocessor system under the assumption that all of the neighbors of any node in the system cannot fail at the same time. This study shows that the conditional diagnosability for k -ary n -cubes under the PMC model is 8 n − 7 for k ≥ 4 and n ≥ 4.

Let F_v be a set of faulty nodes in an n-dimensional hypercube, denoted by Q_n. Also, let F_e be a set of faulty edges in which at least one end-node of each edge is faulty. An edge in Q_n is said to be critical if it is either fault-free or in F_e. In this paper, we prove that, for up to 2n-4 faulty nodes and/or edges, an n-dimensional hypercube contains a fault-free cycle of every even length from 4 to 2^n-2oF_vo in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature.

We consider fault-tolerant embedding, where an n-dimensional faulty hypercube, denoted byQn, acts as the host graph, and the longest fault-free cycle represents the guest graph. LetFvbe a set of faulty nodes inQn. Also, letFebe a set of faulty edges in which at least one end-node of each edge is faulty, and letFebe a set of faulty edges in which the end-nodes of each edge are both fault-free. An edge inQnis said to be critical if it is either fault-free or inFe. In this paper, we prove that there exists a fault-free cycle of length at least 2n-2|Fv| inQn(nges 3) with |Fe| les 2n-5, and |Fv|+|Fe| les 2n-4 , in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature, where only faulty nodes or faulty edges are considered.

A graph G=(V, E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V| in G. Let F/sub v/ and F/sub e/ be the sets of faulty nodes and faulty edges of an n-dimensional Mobius cube MQ/sub n/, respectively, and let F=F/sub v//spl cup/F/sub e/. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to |V-F/sub v/|. In this paper, we show that MQ/sub n/-F contains a fault-free Hamiltonian path when |F|/spl les/n-1 and n/spl ges/1. We also show that MQ/sub n/-F is pancyclic when |F|/spl les/n-2 and n/spl ges/2. Since MQ/sub n/ is regular of degree n, both results are optimal in the worst case.