| Popis: |
A family P of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if P partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of |P| over all path decompositions P of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n2 ≦ k ≦ n24, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)2 ≦ pn(T) ≦ (n2 − 1)4. Moreover, if k is an integer satisfying (i) (n + 1)2 ≦ k ≦ n − 1 or (ii) n < k ≦ (n2 − 1)4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n ≦ k < (n2 − 1)4. |
