Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Note on the Number of Hamiltonian Paths in Strong Tournaments. | A Note on the Number of Hamiltonian Paths in Strong Tournaments Arthur H. Busch Department of Mathematics Lehigh University Bethlehem PA 18105 ahb205@ Submitted Sep 20 2005 Accepted Jan 18 2006 Published Feb 1 2006 Mathematics Subject Classifications 05C20 05C38 Abstract We prove that the minimum number of distinct hamiltonian paths in a strong tournament of order n is 5 3 . A known construction shows this number is best possible when n 1 mod 3 and gives similar minimal values for n congruent to 0 and 2 modulo 3. A tournament T V A is an oriented complete graph. Let hp T be the number of distinct hamiltonian paths in T . directed paths that include every vertex of V . It is well known that hp T 1 if and only if T is transitive and Rédei 3 showed that hp T is always odd. More generally if T is reducible . not strongly connected then there exists a set A c V such that every vertex of A dominates every vertex of V A. If we denote the subtournament induced on a set S as T S then it is easy to see that hp T hp T A hp T V A . Clearly this process can be repeated to obtain hp T hp T Al hp T A2 hp T At where T Al . T At are the strong components of T. As a result we generally consider hp T for strong tournaments T. In particular we wish to find the minimal value of hp T as T ranges over all strong tournaments of order n. Moon 1 bounded this value above and below with the following result. Theorem Moon 1 . Let hp n be the minimum number of distinct hamiltonian paths in a strong tournament of order n 3. Then 8 3 3n-3 K 3n-1 for n 0 mod 3 an-1 hp n 3n-1 for n 1 mod 3 9 3n-5 3n-1 for n 2 mod 3 where a p6 and 3 p5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 N3 1 This lower bound was used by Thomassen 2 to establish a lower bound for the number of hamiltonian cycles in 2-connected tournaments. Theorem Thomassen 2 . Every 2-connected tournament of order n has at least a 32-1 distinct hamiltonian cycles. We shall prove that the upper .
