7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.