Discrete Mathematics & Theoretical Computer Science, Vol 6, No 2 (2004)

Font Size:  Small  Medium  Large

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

P. Mark Kayll


A sequence (ai) of integers is well-spread if the sums ai+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(b 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).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page