Long cycles and paths in distance graphs

For n∈Nn∈N and D⊆ND⊆N, the distance graph PnD has vertex set {0,1,…,n−1}{0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}{ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental 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 DD of order at least 22, there is a constant cDcD such that the greatest common divisor of the integers in DD is 11 if and only if for every nn, PnD has a component of order at least n−cDn−cD if and only if for every n≥cD+3n≥cD+3, PnD has a cycle of order at least n−cDn−cD. Furthermore, we discuss some consequences and variants of this result.