On \((t, r)\) broadcast domination of certain grid graphs (Q6148305)
From MaRDI portal
scientific article; zbMATH DE number 7786744
Language | Label | Description | Also known as |
---|---|---|---|
English | On \((t, r)\) broadcast domination of certain grid graphs |
scientific article; zbMATH DE number 7786744 |
Statements
On \((t, r)\) broadcast domination of certain grid graphs (English)
0 references
11 January 2024
0 references
A generalization of the concept of domination in graphs is \((t, r )\) broadcast domination, which can defined as follows: certain vertices of a graph \(G\) are designated 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. Let \(\mathbb{T}\) be the set of all towers, and define the signal received by a vertex \(v \in V(G)\) from all towers \(w \in \mathbb{ T}\) to be \(f (v) =\sum_{w\in \mathbb{T}}\max(0,t-d(v,w))\). \textit{D. Blessing} et al. [Discrete Appl. Math. 187, 19--40 (2015; Zbl 1315.05098)] 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 minimum cardinality of a \((t, r )\) broadcast on \(G\) is called the \((t, r )\) broadcast domination number of \(G\). In this paper, the authors present some evaluations on the \((t, r )\) broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king's lattice. For example, the \((t, r )\) broadcast domination number of the king's grid graph with \(m\) rows and \(n\) columns equals \(\lceil (n+r-1)/(2t-r) \rceil\) for \(t > r\) and \(m \leq 2(t -r )+1\).
0 references
graph domination
0 references
grid graphs
0 references