Fault-tolerant embedding of linear arrays and rings in the star graph

Document Type



Methods are presented to embed Hamiltonian paths (H-paths) and Hamiltonian cycles (H-cycles) in a star graph Sn in a faulty environment. The models considered include single-processor failure, double-process failure, and multiple-processor failures. All three models are applied to an H-path/cycle, which is formed by visiting all the (n!/4!)S4s in an Sn in a particular order. An optimal embedding is obtained in the case of single-processor failure, wherein the length of the H-path/cycle is shown to be (n! − 2). The multiple-processor failure model is developed based on single and double processor failure models. In this case the length of the H-cycle that can be embedded is shown to be (n! − 2f), where fn − 2 is the number of faults. Another case of multiple-failure scenario is investigated by assuming that all faults are contained in a single Sm, m<n. The network in this case, is shown to reduce to a cluster-star graph. It is proven that it is always possible to formulate an H-cycle of length (n! − m!) in such a network.


Cayley graphs; Computer algorithms; Graph theory; Hamiltonian graph theory; Hypercube networks (Computer networks); Parallel computers; Routing (Computer network management)


Computer and Systems Architecture | Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library