Domination in designs

Abstract

We commence the study of domination in the incidence graphs of combinatorial designs. Let $D$ be a combinatorial design and denote by $\gamma (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 $\gamma =2n$. %We also show that for any symmetric $(v,k,\lambda )$-design it holds that $\gamma \le 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 $\gamma \ge \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\le 15$. The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on $\gamma$. Finally, a number of open questions are proposed.