On constant-weight TSP-tours
Scott Jones ; P. Mark Kayll ; Bojan Mohar ; Walter D. Wallis
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 287-307 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270281 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1203,
     author = {Scott Jones and P. Mark Kayll and Bojan Mohar and Walter D. Wallis},
     title = {On constant-weight TSP-tours},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {287-307},
     zbl = {1052.05063},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1203}
}

Scott Jones; P. Mark Kayll; Bojan Mohar; Walter D. Wallis. On constant-weight TSP-tours. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 287-307. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1203/

[000] [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. | Zbl 0573.05032

[001] [2] B. Bollobás, Modern Graph Theory (Springer, New York, 1998).

[002] [3] P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms (Cambridge University Press, Cambridge, 1994). | Zbl 0806.05001

[003] [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. | Zbl 0063.00874

[004] [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 | Zbl 0870.05018

[005] [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. | Zbl 67.0984.03

[006] [7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998) #DS6. | Zbl 0953.05067

[007] [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). | Zbl 0411.68039

[008] [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.

[009] [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. | Zbl 0499.05049

[010] [11] R.K. Guy, Unsolved Problems in Number Theory (Second edition, Springer, New York, 1994). | Zbl 0805.11001

[011] [12] H. Halberstam and K.F. Roth, Sequences (Second edition, Springer, New York, 1983). | Zbl 0498.10001

[012] [13] P.M. Kayll, Well-spread sequences and edge-labellings with constant Hamilton-weight, submitted.

[013] [14] A. Kotzig, On well spread sets of integers, Centre Res. Math. (Université de Montréal) CRM-161 (1972) 83pp.

[014] [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. | Zbl 0213.26203

[015] [16] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Centre Res. Math. (Université de Montréal) CRM-175 (1972). | Zbl 0213.26203

[016] [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). | Zbl 0563.90075

[017] [18] L. Lovász and M.D. Plummer, Matching Theory (North-Holland, New York, 1986).

[018] [19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. | Zbl 0106.37103

[019] [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. | Zbl 0964.11017

[020] [21] I.Z. Ruzsa, Sumsets of Sidon sets, Acta Arith. 77 (1996) 353-359. | Zbl 0872.11013

[021] [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. | Zbl 58.0268.06

[022] [23] S. Sidon, Über die Fourier Konstanten der Functionen der Klasse Lₚ für p > 1, Acta Sci. Math. (Szeged) 7 (1935) 175-176. | Zbl 61.1120.03

[023] [24] G.J. Simmons, Synch-sets: a variant of difference sets, Congr. Numer. 10 (1974) 625-645. | Zbl 0308.05017

[024] [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. | Zbl 64.0972.04

[025] [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. | Zbl 0760.05088

[026] [27] W.D. Wallis, One-Factorizations (Kluwer, Boston, 1997).

[027] [28] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Australas. J. Combin. 22 (2000) 177-190.

[028] [29] D.B. West, Introduction to Graph Theory (Second edition, Prentice-Hall, Upper Saddle River, NJ, 2001).