TAILIEUCHUNG - Báo cáo toán học: "Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3"

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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học