Parallel Architectures, Algorithms, and Networks, International Symposium on
Download PDF

Abstract

Suppose G is a bipartite graph with two partite sets of equal size. G is said to be strongly hamiltonlaceable if there is a hamiltonian path between any two vertices that belong to the different partite sets, and there is a path of (maximal) length N-2 between any two vertices that belong to the same partite set, where N is the order of G. The star graph is known to be bipartite. In this paper, we show that the n-dimensional star graph, where n\geq 4 is strongly hamiltonian-laceable.
Like what you’re reading?
Already a member?
Get this article FREE with a new membership!