In microprocessor-based systems, such as the cloud computing infrastructure, high reliability is essential. As multiprocessor systems become more widespread and increasingly complex, system-level diagnosis will increasingly be adopted to determine their robustness. In this paper, we consider a pessimistic diagnostic strategy for hypermesh multiprocessor systems under the PMC model. The pessimistic strategy is a diagnostic process whereby all faulty processors are correctly identified and at most one fault-free processor may be misjudged to be a faulty processor. We first determine the pessimistic diagnosability of a hypermesh to be${2}{{n}}({{k}} - {1}) - {{k}}$. We then propose an efficient pessimistic diagnostic algorithm to identify at most${ 2}{{n}}({{k}} - { 1}) - {{k}}$faults in${{O}}({{N}})$time, where${\mbi{k}}$is the radix,${\mbi{n}}$is the number of dimensions, and${{N}} = {{k^n}}$is the total number of processors. This result is superior to the best precise diagnostic algorithm, which runs in${{O}}({{N}}{\log _{{k}}}{{N}})$time. Furthermore, the Cartesian product network, a subgraph of the hypermesh and the proposed algorithm can be employed to determine faults in the product network.

The twisted cube TQnis an alternative to the popular hypercube network and some interesting properties of TQnwere investigated recently. The problem of how to embed cycles into a host graph has attracted a great attention in recent years. However, there are few systematic methods proposed to generate the desired cycles in TQn. In this paper, we provide two kinds of systematic methods of embedding cycles into TQn.

The problem of whether or not there are mutually independent hamiltonian cycles in interconnection networks has attracted a great attention in recent years. In this paper, we will show that most of n-dimensional hypercube-like graphs have two mutually independent hamiltonian cycles. Moreover, we also develop a systematic linear time algorithm for constructing two mutually independent hamiltonian cycles in the n-dimensional hypercube Qn, n > 3.

The hypercube has been widely used as the interconnection network in parallel computers. The crossed cube is a variation of hypercube and preserves many of its desirable properties. The hierarchical crossed cube draws upon constructions used within the hypercube and also the crossed cube. The hierarchical crossed cube is suitable for massively parallel systems with thousands of processors and owns many alluring features, such as symmetry and logarithmic diameter. In this paper, we adopt the concept of Hamiltonian cycles pattern to provide a constructive algorithm to generate a Hamiltonian cycle of the hierarchical crossed cube.

The arrangement graph A/sub n,k/ is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. We improve these results and obtain a stronger and simpler statement. Let n-k/spl ges/2 and F/spl sube/V(A/sub n,k/)/spl cup/E(A/sub n,k/). We prove that A/sub n,k/-F is Hamiltonian if |F|/spl les/k(n-k)-2 and A/sub n,k/-F is Hamiltonian connected if |F|/spl les/k(n-k)-3. These results are optimal.

Abstract In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)‐star graph Sn,k. Assume that F ⊂ V(Sn,k) ∪ E(Sn,k). For n − k ≥ 2, we prove that Sn,k − F is Hamiltonian if |F| ≤ n − 3 and Sn,k − F is Hamiltonian connected if |F| ≤ n − 4. For n − k = 1, Sn,n−1 is isomorphic to the n‐star graph Sn which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. © 2003 Wiley Periodicals, Inc.