# 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

## Access Full Article

top## Abstract

top## How to cite

topScott 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] 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] B. Bollobás, Modern Graph Theory (Springer, New York, 1998).
- [3] P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms (Cambridge University Press, Cambridge, 1994). Zbl0806.05001
- [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] 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] 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] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998) #DS6. Zbl0953.05067
- [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] 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. Zbl0499.05049
- [11] R.K. Guy, Unsolved Problems in Number Theory (Second edition, Springer, New York, 1994). Zbl0805.11001
- [12] H. Halberstam and K.F. Roth, Sequences (Second edition, Springer, New York, 1983). Zbl0498.10001
- [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. Zbl0213.26203
- [16] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Centre Res. Math. (Université de Montréal) CRM-175 (1972). Zbl0213.26203
- [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] 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. Zbl0106.37103
- [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] I.Z. Ruzsa, Sumsets of Sidon sets, Acta Arith. 77 (1996) 353-359. Zbl0872.11013
- [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] 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] G.J. Simmons, Synch-sets: a variant of difference sets, Congr. Numer. 10 (1974) 625-645. Zbl0308.05017
- [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] 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] 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).

## NotesEmbed ?

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