On Hamiltonian paths in distance graphs

Abstract

For a finite set D ⊆ N with gcd(D) = 1, we prove the existence of some n ∈ N such that the distance graph PD n with vertex set {0, 1, . . . , n − 1} in which two vertices u and v are adjacent exactly if |u − v| ∈ D, has a Hamiltonian path with endvertices 0 and n − 1. This settles a conjecture posed by Penso et al. [L.D. Penso, D. Rautenbach, J.L. Szwarcfiter, Long cycles and paths in distance graphs, Discrete Math. 310 (2010) 3417–3420]. © 2011 Elsevier Ltd. All rights reserved.

Topics

    2 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)