Download PDF - On constant-weight TSP-toursAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On constant-weight TSP-tours

Authors 1, 1, 2, 3

Affiliations

  1. Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
  2. Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
  3. Department of Mathematics, Southern Illinois University, Carbondale IL 62901-4408, USA

Abstract

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

ENG
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

Bibliography

  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ₚ 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).
Discussiones Mathematicae Graph Theory
2003/23/2
Export to PBN, Opens in new tab
Pages:
287-307
Main language of publication
English
Received
2001-12-11
Accepted
2002-05-07
Published
2003

DOI: 10.7151/dmgt.1203

Exact and natural sciences