Geodesic
On constant-weight TSP-tours
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 287-307

Voir la notice de l'article provenant de la source Library of Science

Is it possible to label the edges of Kₙ 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 
@article{DMGT_2003_23_2_a6,
     author = {Jones, Scott and Kayll, P. and Mohar, Bojan and Wallis, Walter},
     title = {On constant-weight {TSP-tours}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {287--307},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a6/}
}
TY  - JOUR
AU  - Jones, Scott
AU  - Kayll, P.
AU  - Mohar, Bojan
AU  - Wallis, Walter
TI  - On constant-weight TSP-tours
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 287
EP  - 307
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a6/
LA  - en
ID  - DMGT_2003_23_2_a6
ER  - 
%0 Journal Article
%A Jones, Scott
%A Kayll, P.
%A Mohar, Bojan
%A Wallis, Walter
%T On constant-weight TSP-tours
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 287-307
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a6/
%G en
%F DMGT_2003_23_2_a6
Jones, Scott; Kayll, P.; Mohar, Bojan; Wallis, Walter. On constant-weight TSP-tours. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 287-307. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a6/