DMGT

Discussiones Mathematicae Graph Theory 23(2) (2003) 287-307
DOI: https://doi.org/10.7151/dmgt.1203

ON CONSTANT-WEIGHT TSP-TOURS

Scott Jones

Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
e-mail: jonesso@mso.umt.edu

P. Mark Kayll¹

Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
e-mail: Mark.Kayll@umontana.edu

Bojan Mohar²

Department of Mathematics
University of Ljubljana
Jadranska 19
1000 Ljubljana, Slovenia
e-mail: bojan.mohar@uni-lj.si

Walter D. Wallis

Department of Mathematics
Southern Illinois University
Carbondale IL 62901-4408, USA
e-mail: wdwallis@math.siu.edu

Abstract

Is it possible to label the edges of K_n 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.

References

[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:4<365::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_p 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).

Received 11 December 2001
Revised 7 May 2002

Footnotes:

¹Contact author; on leave at University of Ljubljana-the author thanks the Department of Mathematics and the Institute of Mathematics, Physics and Mechanics for their hospitality.
²Supported in part by the Ministry of Science and Technology of Slovenia, Research Program P1-0507-0101.