## Abstract

A sequence (a_{i}) of integers is well-spread if the sums a _{i} + a_{j}, for i < j, are all different. For a fixed positive integer r, let W_{r}(N) denote the maximum integer n for which there exists a well-spread sequence 0 ≤ a_{1} < ⋯ < a_{n} ≤ N with a_{i} ≡ a_{j} (mod r) for all i, j. We give a new proof that W_{r}(N) < (N/r)^{1/2} + O((N/r)^{1/4}); our approach improves a bound of Ruzsa [Acta. Arith. 65 (1993), 259-283] by decreasing the implicit constant, essentially from 4 to √3. We apply this result to verify a conjecture of Jones et al. from [Discuss. Math. Graph Theory 23 (2003), 287-307]. The application concerns the growth-rate of the maximum label Λ(n) in a 'most-efficient' metric, injective edge-labelling of K_{n} with the property that every Hamilton cycle has the same length; we prove that 2n^{2} - O(n^{3/2}) < Λ(n) < 2n^{2} + O(n^{61/40}).

Original language | English |
---|---|

Pages (from-to) | 401-408 |

Number of pages | 8 |

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 6 |

Issue number | 2 |

State | Published - 2004 |

## Keywords

- Graph labelling
- Hamilton cycle
- Weak Sidon
- Well-spread