DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(2) (2003) 287-307
DOI: 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 Kayll1

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

Bojan Mohar2

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 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.

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 Lp 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:

1Contact 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.
2Supported in part by the Ministry of Science and Technology of Slovenia, Research Program P1-0507-0101.