Domination in designs

MaRDI QIDQ6251539zbMATH OpenFDO

Authors Felix Goldberg, Deepak Rajendraprasad, Rogers Mathew

Publication date 14 May 2014

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Steiner systems in finite geometry (51E10) Finite affine and projective planes (geometric aspects) (51E15)

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 $gammaleq2k$. We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a $STS(v)$ has $gammageqfrac23v-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 $vleq15$. 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.

This page was built for publication: Domination in designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6251539)