Long cycles and paths in distance graphs

For n ∈ N and D ⊆ N , the distance graph P n D has vertex set { 0 , 1 , … , n − 1 } and edge set { i j ∣ 0 ≤ i , j ≤ n − 1 , | j − i | ∈ D } . Note that the important and very well-studied circulant graphs coincide with the regular distance graphs. amental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2 , there is a constant c D such that the greatest common divisor of the integers in D is 1 if and only if for every n , P n D has a component of order at least n − c D if and only if for every n ≥ c D + 3 , P n D has a cycle of order at least n − c D . Furthermore, we discuss some consequences and variants of this result.