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 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!.

It is usually difficult to determine the exact reliability of a complicated network system, and numerical estimation may play a critical role in indicating the likelihood that a systemcan be operational in a specified period of time. In this paper, we propose the definition of localized subcube reliability for hypercube-based networks. Using the random fault model and the probability fault model, we derive exact formulations for the localized first-order subcube reliability in an n-dimensional hypercube, respectively. Numerical results are also presented tovalidate the proposed formulations.

Abstract A graphGis a combinedk‐fault‐tolerant Hamiltonian graph (also called a combinedk‐Hamiltonian graph) ifG−Fis Hamiltonian for every subsetF⊂ (V(G) ∪E(G)) with |F| =k. A combinedk‐Hamiltonian graphGwith |V(G)| =nis optimal if it has the minimum number of edges among alln‐nodek‐Hamiltonian graphs. Using the concept of node expansion, we present a powerful construction scheme to construct a larger combinedk‐Hamiltonian graph from a given smaller graph. Many previous graphs can be constructed by the concept of node expansion. We also show that our construction maintains the optimality property in most cases. The classes of optimal combinedk‐Hamiltonian graphs that we constructed are shown to have a very good diameter. In particular, those optimal combined 1‐Hamiltonian graphs that we constructed have a much smaller diameter than that of those constructed previously by Mukhopadhyaya and Sinha, Harary and Hayes, and Wang et al. © 2001 John Wiley & Sons, Inc.

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. © 2000 John Wiley & Sons, Inc.

We show that the cyclic-cubes defined by Ada W.C. Fu and S.C. Chau (1998) are isomorphic to k-ary wrapped butterfly networks.

The token ring topology is required in the token passing approach used in distributed operating systems. Fault tolerance is also required in the design of distributed systems. We consider the 1-fault-tolerant design for token rings, which can tolerate 1-processor fault- or 1-link fault. Note that the 1-fault-tolerant design for token rings is equivalent to the design of 1-Hamiltonian graphs. The paper introduces a new family of interconnection networks called Christmas tree. The under graph of the Christmas tree, denoted by CT(s), is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes and the diameter of CT(s) are 3/spl times/2/sup s/-2 and 2s, respectively. In other words, the diameter of CT(s) is 2 log/sub 2/ n-O(1), where n is the number of nodes.

Abstract Let G = (V,E) be an undirected graph having an edge weight we ≥ 0 for each e ϵ E. An edge is called a most vital edge (with respect to weighted matching) if its removal from G results in the largest decrease in the total weight of the maximum weighted matching. In this paper, we study the most vital edges of matching in a weighted bipartite graph. We present an O(n3) algorithm to obtain the most vital edges. © 1993 by John Wiley & Sons, Inc.