Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

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 GnD has vertex set { 0,1,…,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.

Full Text: PDF PostScript