A Recurrence for Bounds on Dominating Sets in $k$-Majority Tournaments

Abstract

A $k$-majority tournament is realized by $2k-1$ linear orders on the set of vertices, where a vertex $u$ dominates $v$ if $u$ precedes $v$ in at least $k$ of the orders. Various properties of such tournaments have been studied, among them the problem of finding the size of a smallest dominating set. It is known that $2$-majority tournaments are dominated by $3$ vertices and that $k$-majority tournaments are dominated by $O(k \log k)$ vertices. However, precise values are not known even for $k=3$. We establish new upper bounds for the size of a smallest dominating set in $k$-majority tournaments that considerably improve upon previous bounds for small $k$. In particular our result shows that $3$-majority tournaments are dominated by at most $12$ vertices.