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/

[1] L. Babai and V.T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985) 101-114.

[2] B. Bollobás, Modern Graph Theory (Springer, New York, 1998).

[3] P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms (Cambridge University Press, Cambridge, 1994).

[4] S. Chowla, Solution of a problem of Erdős and Turán in additive-number theory, Proc. Nat. Acad. Sci. India. Sect. A 14 (1944) 1-2.

[5] W.A. Deuber and X. Zhu, Circular colorings of weighted graphs, J. Graph Theory 23 (1996) 365-376, doi: 10.1002/(SICI)1097-0118(199612)23:4365::AID-JGT6>3.0.CO;2-P

[6] P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941) 212-215, doi: 10.1112/jlms/s1-16.4.212.

[7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998) #DS6.

[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979).

[9] S.W. Golomb, How to number a graph, in: R.C. Read, ed., Graph theory and computing (University of the West Indies, Kingston, Jamaica, 1969), Academic Press, New York, 1972, 23-37.

[10] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods 1 (1980) 382-404, doi: 10.1137/0601045.

[11] R.K. Guy, Unsolved Problems in Number Theory (Second edition, Springer, New York, 1994).

[12] H. Halberstam and K.F. Roth, Sequences (Second edition, Springer, New York, 1983).

[13] P.M. Kayll, Well-spread sequences and edge-labellings with constant Hamilton-weight, submitted.

[14] A. Kotzig, On well spread sets of integers, Centre Res. Math. (Université de Montréal) CRM-161 (1972) 83pp.

[15] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970) 451-461, doi: 10.4153/CMB-1970-084-1.

[16] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Centre Res. Math. (Université de Montréal) CRM-175 (1972).

[17] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds., The Traveling Salesman Problem (Wiley, New York, 1985).

[18] L. Lovász and M.D. Plummer, Matching Theory (North-Holland, New York, 1986).

[19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27.

[20] N.C.K. Phillips and W.D. Wallis, Well-spread sequences (Papers in honour of Stephen T. Hedetniemi), J. Combin. Math. Combin. Comput. 31 (1999) 91-96.

[21] I.Z. Ruzsa, Sumsets of Sidon sets, Acta Arith. 77 (1996) 353-359.

[22] S. Sidon, Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen, Math. Ann. 106 (1932) 536-539, doi: 10.1007/BF01455900.

[23] S. Sidon, Über die Fourier Konstanten der Functionen der Klasse Lₚ für p > 1, Acta Sci. Math. (Szeged) 7 (1935) 175-176.

[24] G.J. Simmons, Synch-sets: a variant of difference sets, Congr. Numer. 10 (1974) 625-645.

[25] J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938) 377-385, doi: 10.1090/S0002-9947-1938-1501951-4.

[26] V.T. Sós, An additive problem in different structures, Chap. 45 in: Y. Alavi, F.R.K. Chung, R.L. Graham and D.F. Hsu, eds., Graph theory, combinatorics, algorithms, and applications (San Francisco State University, San Francisco, CA, 1989), SIAM, Philadelphia, 1991, 486-510.

[27] W.D. Wallis, One-Factorizations (Kluwer, Boston, 1997).

[28] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Australas. J. Combin. 22 (2000) 177-190.

[29] D.B. West, Introduction to Graph Theory (Second edition, Prentice-Hall, Upper Saddle River, NJ, 2001).