Path numbers of balanced bipartite tournaments Original Research Article

A path decomposition of a digraph D is a partition of its edge set into edge disjoint simple paths. The minimal number of paths necessary to form a path decomposition is called the path number of D and denoted by pn(D). A bipartite tournament T(A,B) with partition sets A and B is balanced if |A|=|B|=n⩾1. We prove the following: (a) if n is odd and k is any odd integer from the interval [n,n2] or (b) if n is even and k is any even integer from the interval [n/2+1,n2], then there exists a balanced bipartite tournament T(A,B), |A|=|B|=n, with pn(T(A,B))=k.