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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.7--30
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179214
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:15:02
Dernière modification le : lundi 13 novembre 2017 - 15:22:01
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:24:17

Fichier

dmtcs-16-1-2.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01179214, version 1

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 (in progress) (1), pp.7--30. 〈hal-01179214〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

493