# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## ON CONSTANT-WEIGHT TSP-TOURS

 Scott Jones Department of Mathematical SciencesUniversity of MontanaMissoula MT 59812-0864, USAe-mail: jonesso@mso.umt.edu P. Mark Kayll1 Department of Mathematical SciencesUniversity of MontanaMissoula MT 59812-0864, USAe-mail: Mark.Kayll@umontana.edu Bojan Mohar2 Department of MathematicsUniversity of LjubljanaJadranska 191000 Ljubljana, Sloveniae-mail: bojan.mohar@uni-lj.si Walter D. Wallis Department of MathematicsSouthern Illinois UniversityCarbondale IL 62901-4408, USAe-mail: wdwallis@math.siu.edu

## Abstract

Is it possible to label the edges of Kn with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when Hamilton cycle'' is replaced by k-factor'' for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant factor) the growth rate of the maximum edge-label in a most efficient'' injective metric trivial-TSP labelling.

Keywords: graph labelling, complete graph, travelling salesman problem, Hamilton cycle, one-factor, two-factor, k-factor, constant-weight, local matching conditions, edge label growth-rate, Sidon sequence, well-spread sequence.

2000 Mathematics Subject Classification: Primary 05C78; Secondary 05C70, 11B75, 90C27.