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

combinatoricsdirected graphsdiscrete mathematicsextremal-graph-theorygraph theory

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.

Best 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.)