Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 2 | 287-307
Tytuł artykułu

On constant-weight TSP-tours

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
  • Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
  • Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
  • Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
  • Department of Mathematics, Southern Illinois University, Carbondale IL 62901-4408, USA
  • [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).
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.