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