On (t, r) broadcast domination of certain grid graphs

DOI10.2140/INVOLVE.2023.16.883MaRDI QIDQ6148305zbMATH OpenFDO

Authors Natasha Crepeau, Pamela E. Harris, Sean Hays, Marissa Loving, Joseph Rennie, Gordon Rojas Kirby, Alexandro Vasquez

Publication date 11 January 2024

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.06189

zbMATH Keywords

graph dominationgrid graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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 $VsetminusD$ 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 $mathbbT$ be the set of all towers, and we define the signal received by a vertex $vinV(G)$ from a tower $winmathbbT$ to be $f(v)=su{m}_{winmathbbT}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 $mathbbTsubseteqV(G)$ such that $f(v)geqr$ for all $vinV(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.

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 3487529
• scientific article; zbMATH DE number 3080938
• scientific article; zbMATH DE number 3407754
• Eine Bemerkung zum Satz von Vitali über Konvergenz von Funktionenfolgen: Dem stets hilftsbereiten Herrn Kollegen H. L. Schmid, gewidmet
• scientific article; zbMATH DE number 1839786
• Holomorphic mappings of complex manifolds
• scientific article; zbMATH DE number 5593209
• On \(\varepsilon\)-representations
• scientific article; zbMATH DE number 3148394

Cites work

• Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
• On \((t,r)\) broadcast domination numbers of grids
• The \(( t , r )\) broadcast domination number of some regular graphs

Cited in

(1)

• (t, r)-broadcast domination in graphs

This page was built for publication: On \((t, r)\) broadcast domination of certain grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148305)