{
  "id": "1712.00150",
  "version": "v1",
  "published": "2017-12-01T01:54:01.000Z",
  "updated": "2017-12-01T01:54:01.000Z",
  "title": "Computing upper bounds for optimal density of $(t,r)$ broadcasts on the infinite grid",
  "authors": [
    "Benjamin F. Drews",
    "Pamela E. Harris",
    "Timothy W. Randolph"
  ],
  "comment": "7 pages, 2 figures, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "The domination number of a finite graph $G$ with vertex set $V$ is the cardinality of the smallest set $S\\subseteq V$ such that for every vertex $v\\in V$ either $v\\in S$ or $v$ is adjacent to a vertex in $S$. A set $S$ satisfying these conditions is called a dominating set. In 2015 Blessing, Insko, Johnson, and Mauretour introduced $(t,r)$ broadcast domination, a generalization of graph domination parameterized by the nonnegative integers $t$ and $r$. In this setting, we say that the signal a vertex $v\\in V$ receives from a tower of strength $t$ located at vertex $T$ is defined by $sig(v,T)=max(t-dist(v,T),0)$. Then a $(t,r)$ broadcast dominating set on $G$ is a set $S\\subseteq V$ such that the sum of all signal received at each vertex $v \\in V$ is at least $r$. In this paper, we consider $(t,r)$ broadcasts of the infinite grid and present a Python program to compute upper bounds on the minimal density of a $(t,r)$ broadcast on the infinite grid. These upper bounds allow us to construct counterexamples to a conjecture by Blessing et al. that the $(t,r)$ and $(t+1, r+2)$ broadcasts are equal whenever $t,r\\geq 1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-01T01:54:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C12",
      "68R05",
      "68R10"
    ],
    "keywords": [
      "infinite grid",
      "computing upper bounds",
      "optimal density",
      "finite graph",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}