On $(t,r)$ broadcast domination of certain grid graphs
| Autor: | Crepeau, Natasha, Harris, Pamela E., Hays, Sean, Loving, Marissa, Rennie, Joseph, Kirby, Gordon Rojas, Vasquez, Alexandro |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Involve 16 (2023) 883-903 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.2140/involve.2023.16.883 |
| Popis: | Let $G=( V(G), E(G) )$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. We say a subset $D$ of $V(G)$ dominates $G$ if every vertex in $V \setminus D$ is adjacent to a vertex in $D$. A generalization of this concept is $(t,r)$ broadcast domination. We designate certain vertices to be towers of signal strength $t$, which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. We let $\mathbb{T}$ be the set of all towers, and we define the signal received by a vertex $v\in V(G)$ from a tower $w \in \mathbb T$ to be $f(v)=\sum_{w\in \mathbb{T}}max(0,t-d(v,w))$. Blessing, Insko, Johnson, Mauretour (2014) defined a $(t,r)$ broadcast dominating set, or a $(t,r) $ broadcast, on $G$ as a set $\mathbb{T} \subseteq V(G) $ such that $f(v)\geq r$ for all $v\in V(G)$. The minimal cardinality of a $(t, r)$ broadcast on $G$ is called the $(t, r)$ broadcast domination number of $G$. In this paper, we present our research on the $(t,r)$ broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king's lattice. Comment: 17 pages, 16 figures, edited to incorporate referee's comments, to appear in Involve |
| Databáze: | arXiv |
| Externí odkaz: |
|