Hamiltonian Properties on a Class of Circulant Interconnection Networks

Abstract

Classes of circulant graphs play an important role in modeling
interconnection networks in parallel and distributed computing. They
also find applications in modeling quantum spin networks supporting
the perfect state transfer. It has been noticed that unitary Cayley
graphs as a class of circulant graphs possess many good properties
such as small diameter, mirror symmetry, recursive structure,
regularity, etc. and therefore can serve as a model for efficient
interconnection networks. In this paper we go a step further and analyze some other characteristics of unitary Cayley graphs important for the modeling of a good interconnection network. We show that all unitary Cayley graphs are hamiltonian. More precisely, every unitary Cayley graph is hamiltonian-laceable (up to one exception for $X_6$) if it is bipartite, and hamiltonian-connected if it is not. We prove this by presenting an explicit construction of hamiltonian paths on $X_{nm}$ using the hamiltonian paths on $X_n$ and $X_m$ for $\gcd(n,m)=1$. Moreover, we also prove that every unitary Cayley graph is bipancyclic and every nonbipartite unitary Cayley graph is pancyclic.