Hamiltonian Circuits in Sparse Circulant Digraphs

Abstract

A circulant digraph $G(a_1,a_2,\dots ,a_k)$, where $0<a_1<a_2<\dots <a_k<|V(G)|=n$, is the vertex transitive directed graph that has vertices $i+a_1,i+a_2,\dots ,i+a_k(\mathrm{mod}n)$ adjacent to each vertex $i$. We give the necessary and sufficient conditions for $G(a_1,a_2)$ to be hamiltonian, and we prove that $G(a,n-a,b)$ is hamiltonian. In addition, we identify the explicit hamiltonian circuits for a few special cases of sparse circulant digraphs.