2
$\begingroup$

For any positive integer $k$, does there exist a tournament such that the smallest dominating set that forms a transitive subtournament has size exactly $k$?

A tournament that does not work for $k>2$ is one where the vertices are on a cycle and each vertex has an edge to $(n-1)/2$ following vertices clockwise -- in this case taking two opposite vertices already gives a dominating set which is also transitive, meaning $k=2$.

Improve this question
$\endgroup$
1
  • $\begingroup$ Do you mean "which" or "that" in the first sentence? That changes the meaning. Either way though, you should be able to construct it by starting with $k$ vertices and then adding vertices one-by-one such that each newly added vertex $v$ has only one in-neighbor, and that in-neighbor is among the $k$ vertices. After you do this enough many times, the smallest dominating set will be the set you started. $\endgroup$
    – Boris Bukh
    May 29, 2019 at 13:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.