{
  "id": "1711.11116",
  "version": "v1",
  "published": "2017-11-29T21:37:05.000Z",
  "updated": "2017-11-29T21:37:05.000Z",
  "title": "Optimal $(t,r)$ Broadcasts On the Infinite Grid",
  "authors": [
    "Benjamin F. Drews",
    "Pamela E. Harris",
    "Timothy W. Randolph"
  ],
  "comment": "17 pages, 16 figures, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G=(V,E)$ be a graph and $t,r$ be positive integers. The signal that a vertex $v$ receives from a tower of signal strength $t$ located at vertex $T$ is defined as $sig(v,T)=max(t-dist(v,T),0)$, where $dist(v,T)$ denotes the distance between the vertices $v$ and $T$. In 2015 Blessing, Insko, Johnson, and Mauretour defined a $(t,r)$ broadcast dominating set, or simply a $(t,r)$ broadcast, on $G$ as a set $\\mathbb{T}\\subseteq V$ such that the sum of all signal received at each vertex $v \\in V$ is at least $r$. We say that $\\mathbb{T}$ is optimal if $|\\mathbb{T}|$ is minimal among all such sets $\\mathbb{T}$. The cardinality of an optimal $(t,r)$ broadcast on a finite graph $G$ is called the $(t,r)$ broadcast domination number of $G$. The concept of $(t,r)$ broadcast domination generalizes the classical problem of domination on graphs. In fact, the $(2,1)$ broadcasts on a graph $G$ are exactly the dominating sets of $G$. In their paper, Blessing et al. considered $(t,r)\\in\\{(2,2),(3,1),(3,2),(3,3)\\}$ and gave optimal $(t,r)$ broadcasts on $G_{m,n}$, the grid graph of dimension $m\\times n$, for small values of $m$ and $n$. They also provided upper bounds on the optimal $(t,r)$ broadcast numbers for grid graphs of arbitrary dimensions. In this paper, we define the density of a $(t,r)$ broadcast, which allows us to provide optimal $(t,r)$ broadcasts on the infinite grid graph for all $t\\geq2$ and $r=1,2$, and bound the density of the optimal $(t,3)$ broadcast for all $t\\geq2$. In addition, we give a family of counterexamples to the conjecture of Blessing et al. that the optimal $(t,r)$ and $(t+1, r+2)$ broadcasts are identical for all $t\\geq1$ and $r\\geq1$ on the infinite grid.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-29T21:37:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C12",
      "68R05",
      "68R10"
    ],
    "keywords": [
      "broadcast domination number",
      "infinite grid graph",
      "broadcast domination generalizes",
      "gave optimal",
      "finite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}