On competition indices and periods of multipartite tournaments

Abstract

In this paper, we compute competition indices and periods of multipartite tournaments. We first show that the competition period of an acyclic digraph $D$ is one and $\zeta (D)+1$ is a sharp upper bound of the competition index of $D$ where $\zeta (D)$ is the sink elimination index of $D$. Then we prove that, especially, for an acyclic $k$-partite tournament $D$, the competition index of $D$ is $\zeta (D)$ or $\zeta (D)+1$ for an integer $k\ge 3$. By developing useful tools to create infinitely many directed walks in a certain regular pattern from given directed walks, we show that the competition period of a multipartite tournament with sinks and directed cycles is at most three. We also prove that the competition index of a primitive digraph does not exceed its exponent.

20 pages