### On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

*Christian Löwenstein, Dieter Rautenbach, Roman Soták*

#### Abstract

For a positive integer n∈ℕ and a set
D⊆ ℕ, the distance graph
G

_{n}^{D}has vertex set { 0,1,…,n-1} and two vertices i and j of G_{n}^{D}are adjacent exactly if |j-i|∈D. The condition gcd(D)=1 is necessary for a distance graph G_{n}^{D}being connected. Let D={d_{1},d_{2}}⊆ℕ be such that d_{1}>d_{2}and gcd(d_{1},d_{2})=1. We prove the following results.- If n is
sufficiently large in
terms of D, then G
_{n}^{D}has a Hamiltonian path with endvertices 0 and n-1. - If d
_{1}d_{2}is odd, n is even and sufficiently large in terms of D, then G_{n}^{D}has a Hamiltonian cycle. - If d
_{1}d_{2}is even and n is sufficiently large in terms of D, then G_{n}^{D}has a Hamiltonian cycle.

Full Text: PDF PostScript