Jones, Scott; Kayll, P. Mark; Mohar, Bojan; Wallis, Walter D. On constant-weight TSP-tours. (English) Zbl 1052.05063 Discuss. Math., Graph Theory 23, No. 2, 287-307 (2003). The paper looks to labelings of the edges of complete graphs \(K_n\) with distinct integer weights such that each Hamiltonian cycle has exactly the same total weight. The paper shows that such labelings, called { trivial TSP edge-labelings}, exist, and gives a number of equivalent statements for a labeling to be trivial TSP, amongst others: for each 4-cycle with consecutive edges \(e_1, e_2, e_3, e_4\), we have \(w(e_1)+w(e_3) = w(e_2) + w(e_4)\); for each 4-clique in the graph, the total weight for each perfect matching in the clique is identical; for every \(k\), \(0\leq k\leq n-1\), the labeling has constant weight on \(k\)-factors. Related results are also derived. Reviewer: Hans L. Bodlaender (Utrecht) Cited in 2 ReviewsCited in 3 Documents MSC: 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 11B75 Other combinatorial number theory 90C35 Programming involving graphs or networks 05C38 Paths and cycles Keywords:graph labeling; traveling salesman problem; Hamiltonian cycle; \(k\)-factor; complete graph PDFBibTeX XMLCite \textit{S. Jones} et al., Discuss. Math., Graph Theory 23, No. 2, 287--307 (2003; Zbl 1052.05063) Full Text: DOI Link