$(t,r)$ Broadcast Domination Numbers and Densities of the Truncated Square Tiling Graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914922125852672 |
|---|---|
| author | Cervantes, Jillian Harris, Pamela E. |
| author_facet | Cervantes, Jillian Harris, Pamela E. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13331 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $(t,r)$ Broadcast Domination Numbers and Densities of the Truncated Square Tiling Graph Cervantes, Jillian Harris, Pamela E. Combinatorics 05C69, 05C12, 68R05, 68R10 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. |
| title | $(t,r)$ Broadcast Domination Numbers and Densities of the Truncated Square Tiling Graph |
| topic | Combinatorics 05C69, 05C12, 68R05, 68R10 |
| url | https://arxiv.org/abs/2408.13331 |