On \((t, r)\) broadcast domination of certain grid graphs (Q6148305): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: On \((t,r)\) broadcast domination numbers of grids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The \(( t , r )\) broadcast domination number of some regular graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids / rank | |||
Normal rank |
Latest revision as of 09:32, 23 August 2024
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