2-limited broadcast domination on grid graphs

DOI10.1016/J.DAM.2023.05.031MaRDI QIDQ6110604zbMATH OpenFDO

Authors Aaron Slobodin, Gary MacGillivray, Wendy Myrvold

Publication date 2 August 2023

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

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

zbMATH Keywords

broadcast dominationlimited broadcast dominationlimited multipackingmultipacking

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Linear programming (90C05)

Abstract: We establish upper and lower bounds for the 2-limited broadcast domination number of various grid graphs, in particular the Cartesian product of two paths, a path and a cycle, and two cycles. The upper bounds are derived by explicit constructions. The lower bounds are obtained via linear programming duality by finding lower bounds for the fractional 2-limited multipacking numbers of these graphs.

Recommendations

• 2-limited broadcast domination in subcubic graphs
• Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs
• On the multipacking number of grid graphs
• On 2-limited packings of complete grid graphs
• General bounds on limited broadcast domination

Cites work

• A linear‐time algorithm for broadcast domination in a tree
• Broadcast domination and multipacking in strongly chordal graphs
• Broadcast domination and multipacking: bounds and the integrality gap
• Broadcast domination in graphs
• General bounds on limited broadcast domination
• scientific article; zbMATH DE number 6843211 (Why is no real title available?)
• scientific article; zbMATH DE number 2109329 (Why is no real title available?)
• New bounds for the broadcast domination number of a graph
• New upper bounds on the distance domination numbers of grids
• Optimal broadcast domination in polynomial time
• The domination number of grids

Cited in

(7)

• 2-limited dominating broadcasts on cubic graphs without induced 4-cycles
• 2-limited broadcast domination in subcubic graphs
• Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs
• Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
• Upper bounds of k-limited dominating broadcasts for some grid graphs
• Proving exact values for the \(2\)-limited broadcast domination number on grid graphs
• Comments on broadcast algorithms for two-dimensional grids

This page was built for publication: 2-limited broadcast domination on grid graphs

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