Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph GG on nn vertices is called a Dirac graph if it has a minimum degree of at least n/2n/2. The distance distG(u,v) is defined as the number of edges in a shortest path of GG joining uu and vv. In this paper we show that in a Dirac graph GG, for every small enough subset SS of the vertices, we can distribute the vertices of SS along a Hamiltonian cycle CC of GG in such a way that all but two pairs of subsequent vertices of SS have prescribed distances (apart from a difference of at most 1) along CC. More precisely we show the following. There are ω,n0>0ω,n0>0 such that if GG is a Dirac graph on n≥n0n≥n0 vertices, dd is an arbitrary integer with 3≤d≤ωn/23≤d≤ωn/2 and SS is an arbitrary subset of the vertices of GG with 2≤|S|=k≤ωn/d2≤|S|=k≤ωn/d, then for every sequence didi of integers with 3≤di≤d,1≤i≤k−13≤di≤d,1≤i≤k−1, there is a Hamiltonian cycle CC of GG and an ordering of the vertices of SS, a1,a2,…,aka1,a2,…,ak, such that the vertices of SS are visited in this order on CC and we have |distC(ai,ai+1)−di|≤1,for all but one1≤i≤k−1.