Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3. | Hamiltonian paths in the complete graph with edge-lengths 1 2 3 Stefano Capparelli and Alberto Del Fra Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate Sapienza Universita di Roma Via Scarpa 16 I-00161 Roma ITALY capparelli@ .it .it Submitted May 29 2009 Accepted Mar 10 2010 Published Mar 15 2010 Mathematics Subject Classification 05C38 Abstract Marco Buratti has conjectured that given an odd prime p and a multiset L containing p 1 integers taken from 1 . p-1 there exists a Hamiltonian path in the complete graph with p vertices whose multiset of edge-lengths is equal to L modulo p. We give a positive answer to this conjecture in the case of multisets of the type 1a 2b 3c by completely classifying such multisets that are linearly or cyclically realizable. 1 Introduction Given a permutation Ơ a 0 . a n 1 of the set of integers 0 . n 1 we define di a i ơ i 1 i 1 . n 1. We may construct the associated multiset of differences L di . dn-1 In this situation following 1 we say that Ơ is a linear realization of the multiset L. For example Ơ 0 2 5 6 3 1 4 7 9 8 is a linear realization of L 12 23 34 where each exponent denotes the multiplicity of the base element in the multiset L. The following diagram allows us to describe both the multiset of differences and the permutation 025 . 31 o o 479 . 8 Io 6 o 3 We notice however that the sequence of differences does not uniquely determine the permutation. For example THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R44 1 0 2 5 4 1 3 . 6 9 7 . 8 1 is a different realization f the same multiset with the same sequence f differences and the same initial vertex. Let us denote with d1 . dn_i the sequence of signed differences. Once the first vertex is fixed this sequence uniquely determines the permutation Ơ and we found it a useful device in our computation. In this paper we shall choose a 0 0 and sometimes we shall identify the permutation Ơ with the related sequence of signed .
