{
  "id": "1405.3436",
  "version": "v1",
  "published": "2014-05-14T10:19:18.000Z",
  "updated": "2014-05-14T10:19:18.000Z",
  "title": "Domination in designs",
  "authors": [
    "Felix Goldberg",
    "Deepak Rajendraprasad",
    "Rogers Mathew"
  ],
  "categories": [
    "math.CO"
  ],
  "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 \\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-14T10:19:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05B05",
      "51E15",
      "51E10"
    ],
    "keywords": [
      "domination number",
      "steiner triple systems",
      "combinatorial design",
      "incidence graphs",
      "deriving lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.3436G"
    }
  }
}