## Christian Löwenstein ; Dieter Rautenbach ; Roman Soták - On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

dmtcs:1261 - Discrete Mathematics & Theoretical Computer Science, February 4, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1261
On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

Authors: Christian Löwenstein 1; Dieter Rautenbach 1; Roman Soták 2

• 1 Institut für Optimierung und Operations Research
• 2 Institute of Mathematics [Kosice, Slovakia]

For a positive integer n∈ℕ and a set D⊆ ℕ, the distance graph GnD has vertex set &#x007b; 0,1,\textellipsis,n-1&#x007d; 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=&#x007b;d1,d2&#x007d;⊆ℕ 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.

Volume: Vol. 16 no. 1
Section: Graph Theory
Published on: February 4, 2014
Accepted on: July 23, 2015
Submitted on: February 10, 2011
Keywords: Distance graph, circulant graph, Hamiltonian path, Hamiltonian cycle,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

## Linked publications - datasets - softwares

 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.disc.2009.02.017 10.1016/j.disc.2009.02.017 Hamilton cycles and paths in vertex-transitive graphs-Current directions