19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers Fault-Hamiltonicity of Hypercube-Like Interconnection Networks Denver, Colorado April 04-April 08 ISBN: 0-7695-2312-9
We call a graph G to be f-fault hamiltonian (resp. f-fault hamiltonian-connected) if there exists a hamiltonian cycle (resp. if each pair of vertices are joined by a hamiltonian path) in G\F for any set F of faultry elements with |F| ≤ f. In this paper, we deal with the graph G₀ and G₁ with n vertices each by n pairwise nonadjacent edges joining vertices in G₀ and vertices in G₁. Provided each G_i is f-fault hamiltonian-connected and f + 1-fault hamiltonian, 0 ≤ i ≤ 3, we show that G₀ ⊕ G₃. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G₀ ⊕ ₁ connecting two lower dimensional networks G₀ and G₁. Applying our main results to a subclass of hypercube-like interconnection networks, called restricted HL-graphs, which include twisted cubes, crossed cubes, multiply twisted cubes, M?bius cubes, Mcubes, and generalized twisted cubes, we show that every restricted HL-graph of degree m(≥ 3) is m - 3-fault hamiltonian-connected and m - 2-fault hamiltonian.
Citation:
Jung-Heum Park, Hee-Chul Kim, Hyeong-Seok Lim, "Fault-Hamiltonicity of Hypercube-Like Interconnection Networks," ipdps, vol. 1, pp.60a, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||