A graph$G$is$k$-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most$k$vertices and/or edges from$G$, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let$\delta_{i}$be the minimum degree of$G_{i}$for$i=0$, 1. Given$(\delta_{i}-2)$-fault Hamiltonian and$(\delta_{i}-3)$-fault Hamiltonian-connected graph$G_{i}$for$i=0, 1$, this study shows that the Cartesian product network$G_{0} \times G_{1}$is$(\delta_{0}+\delta_{1}-2)$-fault Hamiltonian and$(\delta_{0}+\delta_{1}-3)$-fault Hamiltonian-connected. We then apply the result to determine the fault-tolerant Hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. This study also demonstrates that these results are worst-case optimal with respect to the number of faults tolerated.

In this paper, we consider two embedding problems in Cartesian product networks: one is the pancycle problem, which involves embedding cycles of various lengths in the given product network; and the other is the panconnectivity problem, which involves embedding paths of various lengths between any pair of distinct nodes in the given product network. We then apply our technical lemmas and theorems to derive new topological properties of two multiprocessor systems, namely, generalized hypercubes and nearest neighbor mesh hypercubes.

A graph G is called k-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most k vertices and/or edges from G, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let δ(G) be the minimum degree of G. Given a (δ(G) - 2)-fault Hamiltonian/ (δ(G) - 3)-fault Hamiltonian-connected graph G and a (δ(H) - 2)-fault Hamiltonian/(δ(H) - 3)-fault Hamiltonian-connected graph H, we show that the Cartesian product network G × H is (δ(G) + δ(H) - 2)-fault Hamiltonian and (δ(G)+δ(H) - 3)-fault Hamiltonian-connected. We then apply our result to determine the fault-tolerant hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. We also demonstrate that our results are worst-case optimal with respect to the number of faults tolerated.

Abstract In this article, we study some topological properties of k‐ary n‐cubes Q . We show that each edge in Q lies on a cycle of every length from k to kn. We also show that Q is both bipanconnected and edge‐bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer. © 2009 Wiley Periodicals, Inc. NETWORKS 2009

The k-ary n-cube, denoted by Qnk, has been one of the most common interconnection networks. In this paper, we study some topological properties of Qnk. Given two arbitrary distinct nodes x and y in Qnk, we show that there exists an x–y path of every length from [k/2]n to kn− 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Qnklies on a cycle of every length from k to kn. In addition, we show that Qnkis both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.