Twin domination number of Tournaments

Abstract

Let $D=(V,A)$ be a digraph. A subset $S$ of $V$ is called a twin dominating set of $D$ if for every vertex $v\in V-S$, there exists vertices $u_1,u_2\in S$ such that $(v,u_1)$ and $(u_2,v)$ are arcs in $D$. The minimum cardinality of a twin dominating set in $D$ is called the twin domination number of $D$ and is denoted by ${\gamma }^{\ast }(D)$. The upper orientable twin domination number of a graph $G$ is $DO{M}^{\ast }(G)=\max \{{\gamma }^{\ast }(D)|D\text{is an orientation of G}\}.$ It has been conjectured that for the complete graph $K_n$ with $n\ge 8$, $DO{M}^{\ast }(K_n)=\lceil \frac{n+1}{2}\rceil$. In this work we prove $DO{M}^{\ast }(K_8)=DO{M}^{\ast }(K_9)=4$ and establish new upper bounds for $DO{M}^{\ast }(K_n)$, disproving the same above conjecture for all $n\ge 8$.

13 pages, 7 figures