Broadcast domination of products of graphs.
Boštjan Brešar, Simon Špacapan · Ars Combinatoria · 2009
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 γ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, γb(G) ≥ ⌈2rad(G)/3⌉. 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.