PL EN


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
EN
Abstrakty
EN
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.
Twórcy
autor
  • Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
  • Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
autor
  • Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
  • Department of Mathematics, Southern Illinois University, Carbondale IL 62901-4408, USA
Bibliografia
  • [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
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1203
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ć.