Graph explorer

Domination in designs

We commence the study of domination in the incidence graphs of combinatorial designs. Let $D$ be a combinatorial design and denote by $γ(D)$ the domination number of the incidence (Levy) graph of $D$. We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order $n$, which is a symmetric $(n^{2}+n+1,n+1,1)$-design, has $γ=2n$. %We also show that for any symmetric $(v,k,λ)$-design it holds that $γ\leq 2k$. We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a $STS(v)$ has $γ\geq \frac{2}{3}v-1$ and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on $v$ vertices have the same domination number is proposed and is verified up to $v \leq 15$. The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on $γ$. Finally, a number of open questions are proposed.