Domination in designs

Felix Goldberg, Deepak Rajendraprasad, Rogers Mathew

Published 2014-05-14Version 1

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 \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 $\gamma \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 $\gamma$. Finally, a number of open questions are proposed.