https://hal.inria.fr/hal-01179214Löwenstein, ChristianChristianLöwensteinInstitut für Optimierung und Operations Research - Universität Ulm - Ulm University [Ulm, Allemagne]Rautenbach, DieterDieterRautenbachInstitut für Optimierung und Operations Research - Universität Ulm - Ulm University [Ulm, Allemagne]Soták, RomanRomanSotákInstitute of Mathematics [Kosice, Slovakia] - P.J. Safarik UniversityOn Hamiltonian Paths and Cycles in Sufficiently Large Distance GraphsHAL CCSD2014Distance graphcirculant graphHamiltonian pathHamiltonian cycle[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Lowinger, Hélène2015-07-22 09:15:022019-03-04 13:44:092015-07-22 09:17:34enJournal articleshttps://hal.inria.fr/hal-01179214/document10.46298/dmtcs.12611For a positive integer n∈ℕ and a set D⊆ ℕ, the distance graph GnD has vertex set { 0,1,\textellipsis,n-1} and two vertices i and j of GnD are adjacent exactly if |j-i|∈D. The condition gcd(D)=1 is necessary for a distance graph GnD being connected. Let D={d1,d2}⊆ℕ be such that d1>d2 and gcd(d1,d2)=1. We prove the following results. If n is sufficiently large in terms of D, then GnD has a Hamiltonian path with endvertices 0 and n-1. If d1d2 is odd, n is even and sufficiently large in terms of D, then GnD has a Hamiltonian cycle. If d1d2 is even and n is sufficiently large in terms of D, then GnD has a Hamiltonian cycle.