A tournement is a directed graph such that for every pair of distinct vertices $\{x,y\}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$x\to y$" to mean "there is an edge from $x$ to $y$."
A dominating set of a directed graph is a subset $S$ of vertices such that for every $t\notin S$, there exists $s\in S$ so $s\to t$.
It can be shown$^*$ that every tournament on $2^{n+1}-2$ vertices has a dominating set of size $n$. My question is whether this result is tight.
Does there exist a tournament on $2^{n+1}-1$ vertices with no dominating set of size $n$?
If not, what is the smallest tournament with no dominating set of size $n$?
My thoughts:
A necessary condition for a graph on $2^{n+1}-1$ vertices with no dominating set of size $n$ is that every vertex must have an out-degree of exactly $2^n-1$, so exactly half of its edges are outgoing.
The answer is yes when $n=1,2$.
- The "rock-paper-scissors" graph on three vertices has no dominating set of size $1$.
- The graph on $\mathbb Z/7\mathbb Z$ where each $x$ has directed edges to $x+1,x+2$ and $x+4\pmod7$ has no dominating set of size $2$.
For $n\ge 3$, the possibilities get too large, and I cannot come up with a clever solution. Can anyone see a pattern?
I came up with this problem while thinking about this puzzle.
$^*$Consider a vertex $s$ with maximal out-degree. By the hand-shaking lemma, this degree must be at least $(2^{n+1}-3)/2$, so at least $2^n-1$. Include $s$ in $S$, then ignore $s$ and the vertices $t$ for which $s\to t$. What remains is tournament of size $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceed by induction.
