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.