Well-spread sequences and edge-labellings with constant Hamilton-weight

Research output: Contribution to journalArticlepeer-review

Abstract

A sequence (ai) of integers is well-spread if the sums a i + aj, for i < j, are all different. For a fixed positive integer r, let Wr(N) denote the maximum integer n for which there exists a well-spread sequence 0 ≤ a1 < ⋯ < an ≤ N with ai ≡ aj (mod r) for all i, j. We give a new proof that Wr(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 Kn with the property that every Hamilton cycle has the same length; we prove that 2n2 - O(n3/2) < Λ(n) < 2n2 + O(n61/40).

Original languageEnglish
Pages (from-to)401-408
Number of pages8
JournalDiscrete Mathematics and Theoretical Computer Science
Volume6
Issue number2
StatePublished - 2004

Keywords

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

Fingerprint

Dive into the research topics of 'Well-spread sequences and edge-labellings with constant Hamilton-weight'. Together they form a unique fingerprint.

Cite this