Distributing pairs of vertices on Hamiltonian cycles
Résumé
AbstractLet G be a graph of order n with minimum degree $$\delta (G) \geqslant \tfrac{n}
{2} + 1$$δ(G)⩾n2+1. Faudree and Li (2012) conjectured that for any pair of vertices x and y in G and any integer $$2 \leqslant k \leqslant \tfrac{n}
{2}$$2⩽k⩽n2, there exists a Hamiltonian cycle C such that the distance between x and y on C is k. In this paper, we prove that this conjecture is true for graphs of sufficiently large order. The main tools of our proof are the Regularity lemma of Szemerédi and the Blow-up lemma of Komlós et al. (1997).