Conditional Edge-Fault Hamiltonian-Connectivity of Restricted Hypercube-Like Networks

Abstract

A graph G is said to be conditional k-edge-fault hamiltonian-connected if after removing k faulty edges from G under the assumption that each node is incident to at least three fault-free edges there exists a hamiltonian path between any two distinct nodes in the resulting graph In this thesis we consider the conditional edge-fault hamiltonian-connectivity of a wide class of interconnection networks called restricted hypercube-like networks (RHLs) We proved that an n-dimensional RHL (RHLn) is conditional (2n-7)-edge-fault hamiltonian-connected for n >= 6 We then apply our technical theorems to show that several multiprocessor systems including n-dimensional crossed cubes n-dimensional twisted cubes for odd n n-dimensional locally twisted cubes n-dimensional generalized twisted cubes n-dimensional M?bius cubes and recursive circulants G(2^n 4) for odd n are all conditional (2n-7)-edge-fault hamiltonian-connected

Date of Award	2014 Aug 24
Original language	English
Supervisor	Sun-Yuan Hsieh (Supervisor)