Broadcast Domination of Products of Graphs

Abstract

Broadcast domination in graphs is a variation of domination in which different integer weights are allowed on vertices and a vertex with weight \(k\) dominates its distance \(k\)-neighborhood. A distribution of weights on vertices of a graph \(G\) is called a dominating broadcast, if every vertex is dominated by some vertex with positive weight. The broadcast domination number \(\gamma_b(G)\) of a graph \(G\) is the minimum weight (the sum of weights over all vertices) of a dominating broadcast of \(G\). In this paper, we prove that for a connected graph \(G\), \(\gamma_b(G) \geq \lceil{2\text{rad}(G)}/{3}\rceil\). This general bound and a newly introduced concept of condensed dominating broadcast are used in obtaining sharp upper bounds for broadcast domination numbers of three standard graph products in terms of broadcast domination numbers of factors. A lower bound for a broadcast domination number of the Cartesian product of graphs is also determined, and graphs that attain it are characterized. Finally, as an application of these results, we determine exact broadcast domination numbers of Hamming graphs and Cartesian products of cycles.