The h-extra node-connectivity of a graph G is the size of a minimal node-set, whose removal will disconnect G, but each remaining component has no fewer h + 1 nodes. Based on h-extra node-connectivity, the h-extra conditional fault-diagnosability of networks has been proposed for a better, more realistic measure of networks' fault-tolerability. It is the maximal x such that G is h-extra conditionally x-fault-diagnosable. This paper will establish a relationship between the h-extra node-connectivity and h-extra conditional fault-diagnosability for a regular graph G, under the classic PMC diagnostic model. We will apply the newly found relationship to a variety of well-known regular networks, to directly obtain their h-extra conditional fault-diagnosability. The significance of the paper's work is that it relates the notions of h-extra node-connectivity and h-extra conditional fault-diagnosability, so that a regular network's h-extra conditional fault-diagnosability may be known once its h-extra node-connectivity is known.

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.

The g-restricted connectivity (g-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least g neighbors in its respective component. The g-RC is a deterministic indicator of tolerability of a network with failing processors. The g-good-neighbor fault diagnosability (g-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer g good neighbors. This paper establishes the relationship between g-RC and g-GNFD of general regular networks, first under the PMC model and second under the MM* model. Moreover, this paper directly gives the g-GNFD of some well-known special networks by their g-RC and our proposed relationship.

Extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Given a graph G and a non-negative integer g, the g-extra edge connectivity of G is the minimum cardinality of an edge subset in G, if it exists, whose deletion disconnects G and causes every remaining component to have more than g vertices. This paper shows that the 3-extra edge connectivity of an n-dimensional hypercube-like network is for .