The score sequences with unique tournament that has minimum number of upsets

Abstract

Let $T$ be a tournament with nondecreasing score sequence $R$ and $A$ be its tournament matrix. An upset of $T$ corresponds to an entry above the main diagonal of $A$. Given a feasible score sequence $R$, Fulkerson~(1965) gave a simple recursive construction for a tournament with score sequence $R$ and the minimum number of upsets, and Hacioglu et al. (2019) provided a construction for all of such tournament matrices. Let $U_{\min }(R)$ denote the set of tournament matrices with score sequence $R$ that have minimum number of upsets. Brauldi and Li~(1983) characterized the strong score sequences $R$ ($R$ is strong if a tournament $T$ with score sequence $R$ is strongly connected) with $|U_{\min }(R)|=1$. In this article, we characterize all feasible score sequences $R$ with $|U_{\min }(R)|=1$ and give an explicit formula for the number of the feasible score sequences $R$ with $|U_{\min }(R)|=1$.

12 pages