Path numbers of tournaments |
| |
Authors: | Brian Alspach David W Mason Norman J Pullman |
| |
Institution: | Simon Fraser University, Burnaby V5A 1S6, Canada;Directorate of Logistics Analysis, National Defence Headquarters, Ottawa, Canada;Jeffery Hall, Queen''s University, Kingston K7L 3N6, Canada |
| |
Abstract: | A family
of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if
partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of |
| over all path decompositions
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 n/2 k n2/4, 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|