System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the test-based diagnosis with a processor performing the diagnosis by testing the neighboring processors via the links between them. In this paper, we discuss the diagnosability of a ( K 4 – { e})-free graph under the PMC model.

We propose two new measures of conditional connectivity to be the extension of R g -connectivity and R g -edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional ( g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg G–F ( p) + deg G–F ( q) ≥ 2 g + k for every two distinct vertices p and q in G – F with d( p, q) ≤ d. The ( g, d, k)-conditional(-edge)-connectivity, denoted by κ g,d,k ( λ g,d,k ), is the minimum cardinality of a conditional ( g, d, k)(-edge)-cut. Based on these requirements, we obtain κ 1,1, k , κ 1, d,2 , λ 1,1,1 and λ 1, d,2 for the hypercubes.

The study of cycle embedding is an important topic in studying the structures of interconnection networks. In this paper, we study the cycles embedding in pancake graphs. We show that every edge in the n-dimensional pancake graph lies on the cycle with every length between 7 to n!.

An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t-1)°-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(logN)2) with our algorithm, where N is the total number of the processors in the network.

Abstract The alternating group graph AGn is an interconnection network topology based on the Cayley graph of the alternating group. There are some interesting results concerning the hamiltonicity and the fault tolerant hamiltonicity of the alternating group graphs. In this article, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y) ≤ l ≤ ∣V(G)∣−d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x, y on C is l. We show that AGn is panpositionable hamiltonian if n ≥ 3. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 146–156 2007