# Dominating sets in tournaments; is $2^{n+1}-2$ tight?

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.

## 1 Answer

The answer to your question is yes: if $$f(n)$$ is the least number of vertices in a tournament with no $$n$$-vertex dominating set, then $$f(n) > 2^{n+1}-1$$ for large $$n$$ and in general we know $$(n+2) 2^{n-1} - 1 \le f(n) \le C \cdot n^2 \cdot 2^n$$ for some constant $$C$$. Already for $$n=3$$ there is a $$19$$-vertex tournament with no dominating set of size $$3$$: the quadratic residue tournament mod $$19$$. (Here, we have an edge from $$i$$ to $$j$$ if there is some $$k$$ such that $$i + k^2 \equiv j \pmod{19}$$; it is a generalization of your $$7$$-vertex construction.)

(For more details, see for example this paper by Szekeres and Szekeres.)