Affordable Access

Publisher Website

On embedding rings into a star-related network

Authors
Journal
Information Sciences
0020-0255
Publisher
Elsevier
Publication Date
Volume
99
Identifiers
DOI: 10.1016/s0020-0255(96)00280-0

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.