Hamiltonian Circuits in Sparse Circulant Digraphs

Abstract

A circulant digraph \(G(a_1, a_2, \ldots, a_k)\), where \(0 < a_1 < a_2 < \ldots < a_k < |V(G)| = n\), is the vertex transitive directed graph that has vertices \(i+a_1, i+a_2, \ldots, i+a_k \pmod{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.