Hamilton cycles in circulant digraphs with prescribed number of distinct jumps

摘要

Let G be a digraph that consists of a finite set of vertices V(G). G is called a circulant digraph if its automorphism group contains a |V(G)|-cycle. A circulant digraph G has arcs (i, i+a_1 ), (i, i+a_2 ), ... , (i, i +a_j) (mod|V (G)|) incident to each vertex i, where integers a_ks satisfy 0 ＜ a_1 ＜а_2 ＜a_j≤| V(G)| —1 and are called jumps. It is well known that not every G is Hamiltonian. In this paper we give sufficient conditions for a G to have a Hamilton cycle with prescribed distinct jumps, and prove that such conditions are also necessary for every G with two distinct jumps. Finally, we derive several results for obtaining G' with k, k ≥ 2 distinct jumps if the corresponding G contains a Hamilton cycle with two distinct jumps.