On embedding rings into a star-related network

Document Type



It is shown that, in the star graph, it is always possible to form a Hamiltonian path between two nodes as long as the distance between them is odd. This result leads to the proof of Hamiltonicity for the clustered-star graph. The results can readily be used in optimal embedding of a linear array of processors (or a ring) in the star graph. The embedding problem is also solved when one or more processors are faulty in the network. The length of the linear array and the ring in this case is shown to be (n!−m!) where m is the dimension of the smallest star graph which contains all the faulty processors.


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


Computer and Systems Architecture | 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