For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.

Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$. From what I've been able to find, not much is known about $f$. We know $f(2) = 3, f(3) = 7$ and $f(4) = 19$. Past that we're lost. Results from Erdos and Szekeres-Szekeres showed that $$(k + 1) 2^{k - 2} - 1 \leq f(k) \leq (k - 1)^2 2^{k -1} C$$

(for suitable constant $C$) some 50 years ago, and I haven't any refinement of those bounds (except that $f(5) > 47$, showing the lower bound is not exact).

I'm interested in the structural properties of a tournament $T$ of order $f(k)$ having $\gamma(T) = k$, but I can't find much except this paper : Domination and irredundance in tournaments and its references. Any references that describe $T$ would be helpful.

In particular, I'm interested in the existence/non-existence of a constant $c$ that satisfies this statement for any $k$ (and for a large enough tournament) :

Let $T$ be a tournament of order $f(k)$ having $\gamma(T) = k$. Then, for any set $U \subseteq V(T)$ with $|U| = k - c$, there exists a set $U' \subseteq V(T) \setminus U$ of cardinality $c$ such that $U \cup U'$ is a dominating set.

In other words, pick any $k - c$ vertices. Then there's some smallest dominating set that contains them. This doesn't hold for $c = 0$, but it makes intuitive sense that it does for $c = 1$. However, I'm not even close to showing this is true for some constant, neither that there there is a $c$ for which the statement holds for every $k$, but for at least one smallest tournament with domination number $k$.


Your Answer

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

Browse other questions tagged or ask your own question.