{
  "id": "2408.13331",
  "version": "v1",
  "published": "2024-08-23T18:43:26.000Z",
  "updated": "2024-08-23T18:43:26.000Z",
  "title": "$(t,r)$ Broadcast Domination Numbers and Densities of the Truncated Square Tiling Graph",
  "authors": [
    "Jillian Cervantes",
    "Pamela E. Harris"
  ],
  "comment": "32 pages, 27 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a pair of positive integer parameters $(t,r)$, a subset $T$ of vertices of a graph $G$ is said to $(t,r)$ broadcast dominate a graph $G$ if, for any vertex $u$ in $G$, we have $\\sum_{v\\in T, u\\in N_t(v)}(t-d(u,v))\\geq r$, where where $N_{t}(v)=\\{u\\in V:d(u,v)<t\\}$ and $d(u,v)$ denotes the distance between $u$ and $v$. This can be interpreted as each vertex $v$ of $T$ sending $\\max(t-\\text{d}(u,v),0)$ signal to vertices within a distance of $t-1$ away from $v$. The signal is additive and we require that every vertex of the graph receives a minimum reception $r$ from all vertices in $T$. For a finite graph the smallest cardinality among all $(t,r)$ broadcast dominating sets of a graph is called the $(t,r)$ broadcast domination number. We remark that the $(2,1)$ broadcast domination number is the domination number and the $(t,1)$ (for $t\\geq 1$) is the distance domination number of a graph. We study a family of graphs that arise as a finite subgraph of the truncated square titling, which utilizes regular squares and octagons to tile the Euclidean plane. For positive integers $m$ and $n$, we let $H_{m,n}$ be the graph consisting of $m$ rows of $n$ octagons (cycle graph on $8$ vertices). For all $t\\geq 2$, we provide lower and upper bounds for the $(t,1)$ broadcast domination number for $H_{m,n}$ for all $m,n\\geq 1$. We give exact $(2,1)$ broadcast domination numbers for $H_{m,n}$ when $(m,n)\\in\\{(1,1),(1,2),(1,3),(1,4),(2,2)\\}$. We also consider the infinite truncated square tiling, denoted $H_{\\infty,\\infty}$, and we provide constructions of infinite $(t,r)$ broadcasts for $(t,r)\\in\\{(2,1),(2,2),(3,1),(3,2),(3,3),(4,1)\\}$. Using these constructions we give upper bounds on the density of these broadcasts i.e., the proportion of vertices needed to $(t,r)$ broadcast dominate this infinite graph. We end with some directions for future study.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-23T18:43:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C12",
      "68R05",
      "68R10"
    ],
    "keywords": [
      "broadcast domination number",
      "truncated square tiling graph",
      "broadcast dominate",
      "upper bounds",
      "positive integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}