On constant-weight TSP-tours

Scott Jones; P. Mark Kayll; Bojan Mohar; Walter D. Wallis

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 287-307
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Scott Jones, et al. "On constant-weight TSP-tours." Discussiones Mathematicae Graph Theory 23.2 (2003): 287-307. <http://eudml.org/doc/270281>.

@article{ScottJones2003,
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.},
author = {Scott Jones, P. Mark Kayll, Bojan Mohar, Walter D. Wallis},
journal = {Discussiones Mathematicae Graph Theory},
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; graph labeling; traveling salesman problem; Hamiltonian cycle; -factor},
language = {eng},
number = {2},
pages = {287-307},
title = {On constant-weight TSP-tours},
url = {http://eudml.org/doc/270281},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Scott Jones
AU - P. Mark Kayll
AU - Bojan Mohar
AU - Walter D. Wallis
TI - On constant-weight TSP-tours
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 287
EP - 307
AB - 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.
LA - eng
KW - 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; graph labeling; traveling salesman problem; Hamiltonian cycle; -factor
UR - http://eudml.org/doc/270281
ER -

References

top
  1. [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. Zbl0573.05032
  2. [2] B. Bollobás, Modern Graph Theory (Springer, New York, 1998). 
  3. [3] P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms (Cambridge University Press, Cambridge, 1994). Zbl0806.05001
  4. [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. Zbl0063.00874
  5. [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 Zbl0870.05018
  6. [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. Zbl67.0984.03
  7. [7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998) #DS6. Zbl0953.05067
  8. [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). Zbl0411.68039
  9. [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. [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. Zbl0499.05049
  11. [11] R.K. Guy, Unsolved Problems in Number Theory (Second edition, Springer, New York, 1994). Zbl0805.11001
  12. [12] H. Halberstam and K.F. Roth, Sequences (Second edition, Springer, New York, 1983). Zbl0498.10001
  13. [13] P.M. Kayll, Well-spread sequences and edge-labellings with constant Hamilton-weight, submitted. 
  14. [14] A. Kotzig, On well spread sets of integers, Centre Res. Math. (Université de Montréal) CRM-161 (1972) 83pp. 
  15. [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. Zbl0213.26203
  16. [16] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Centre Res. Math. (Université de Montréal) CRM-175 (1972). Zbl0213.26203
  17. [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). Zbl0563.90075
  18. [18] L. Lovász and M.D. Plummer, Matching Theory (North-Holland, New York, 1986). 
  19. [19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. Zbl0106.37103
  20. [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. Zbl0964.11017
  21. [21] I.Z. Ruzsa, Sumsets of Sidon sets, Acta Arith. 77 (1996) 353-359. Zbl0872.11013
  22. [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. Zbl58.0268.06
  23. [23] S. Sidon, Über die Fourier Konstanten der Functionen der Klasse Lₚ für p > 1, Acta Sci. Math. (Szeged) 7 (1935) 175-176. Zbl61.1120.03
  24. [24] G.J. Simmons, Synch-sets: a variant of difference sets, Congr. Numer. 10 (1974) 625-645. Zbl0308.05017
  25. [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. Zbl64.0972.04
  26. [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. Zbl0760.05088
  27. [27] W.D. Wallis, One-Factorizations (Kluwer, Boston, 1997). 
  28. [28] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Australas. J. Combin. 22 (2000) 177-190. 
  29. [29] D.B. West, Introduction to Graph Theory (Second edition, Prentice-Hall, Upper Saddle River, NJ, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.