Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance dist(G)(u, v) is defined as the number of edges in a shortest path of G joining it and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are omega, n(0) > 0 such that if G is a Dirac graph on n >= n(0) vertices, d is all arbitrary integer with 3 <= d <= omega n/2 and S is an arbitrary subset of the vertices of G with 2 <= |S| = k <= wn/d, then for every sequence d(i) of integers with 3 <= d(i) <= d, 1 <= i <= k - 1, there is a Hamiltonian cycle C of G and all ordering of the vertices of S, a(1), a(2),...., a(k), such that the vertices of S are visited in this order on C and we have |dist(C) (a(i), a(i)+ 1) - d(i) | <= 1, for all but one 1 <= i <= k - 1 (C) 2007 Elsevier B.V. All rights reserved.