Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

Abstract : For 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179214
Contributor : Hélène Lowinger Connect in order to contact the contributor
Submitted on : Wednesday, July 22, 2015 - 9:15:02 AM
Last modification on : Monday, March 4, 2019 - 1:44:09 PM
Long-term archiving on: : Friday, October 23, 2015 - 10:24:17 AM

File

dmtcs-16-1-2.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Christian Löwenstein, Dieter Rautenbach, Roman Soták. On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (1), pp.7--30. ⟨10.46298/dmtcs.1261⟩. ⟨hal-01179214⟩

Share

Metrics

Record views

54

Files downloads

636