On (t,r) broadcast domination numbers of grids

DOI10.1016/J.DAM.2015.02.005MaRDI QIDQ2348050zbMATH OpenOpenAlexFDO

Authors David Blessing, Katie Johnson, Christie Mauretour, Erik Insko

Publication date 10 June 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\((t,r)\) broadcast domination numberdistance domination numberdomination numbergrid graphs

Mathematics Subject Classification ID

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

Abstract: The domination number of a graph $G=(V,E)$ is the minimum cardinality of any subset $SsubsetV$ such that every vertex in $V$ is in $S$ or adjacent to an element of $S$. Finding the domination numbers of $m$ by $n$ grids was an open problem for nearly 30 years and was finally solved in 2011 by Goncalves, Pinlou, Rao, and Thomass'e. Many variants of domination number on graphs have been defined and studied, but exact values have not yet been obtained for grids. We will define a family of domination theories parameterized by pairs of positive integers $(t,r)$ where $1leqrleqt$ which generalize domination and distance domination theories for graphs. We call these domination numbers the $(t,r)$ broadcast domination numbers. We give the exact values of $(t,r)$ broadcast domination numbers for small grids, and we identify upper bounds for the $(t,r)$ broadcast domination numbers for large grids and conjecture that these bounds are tight for sufficiently large grids.

Recommendations

• Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids
• Efficient \(( t , r )\) broadcast dominating sets of the triangular lattice
• The \(( t , r )\) broadcast domination number of some regular graphs
• Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
• Optimal \((t, r)\) broadcasts on the infinite grid

Cites work

• R -Domination in Graphs
• \((k,r)\)-domination in graphs
• A note on power domination in grid graphs
• Broadcasts in graphs
• Computing the domination number of grid graphs
• scientific article; zbMATH DE number 3902703 (Why is no real title available?)
• scientific article; zbMATH DE number 4039319 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1124605 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• scientific article; zbMATH DE number 2114690 (Why is no real title available?)
• The domination number of grids
• The domination numbers of the 5 × n and 6 × n grid graphs

Cited in

(12)

• Optimal \((t, r)\) broadcasts on the infinite grid
• The \(( t , r )\) broadcast domination number of some regular graphs
• Efficient \(( t , r )\) broadcast dominating sets of the triangular lattice
• Distance domination in graphs
• Projects in \((t,r)\) broadcast domination
• Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
• Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids
• Games on Graphs: Cop and Robber, Hungry Spiders, and Broadcast Domination
• On \((t, r)\) broadcast domination of certain grid graphs
• Proving exact values for the \(2\)-limited broadcast domination number on grid graphs
• (t, r)-broadcast domination in graphs
• (t,r) broadcast domination numbers and densities of the truncated square tiling graph

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: On \((t,r)\) broadcast domination numbers of grids

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