Broadcast domination of lexicographic and modular products of graphs. Issue 3 (2nd September 2022) - Sen, Jishnu; Kola, Srinivasa Rao
Abstract: A dominating broadcast labeling of a graph G is a function f : V ( G ) → { 0, 1, 2, …, diam ( G ) } such that f ( v ) ≤ e ( v ) for all v ∈ V ( G ), where e ( v ) is the eccentricity of v, and for every vertex u ∈ V ( G ), there exists a vertex v with f ( v ) ≥ 1 and d ( u, v ) ≤ f ( v ) . The cost of f is ∑ v ∈ V ( G ) f ( v ) . The minimum of costs over all the dominating broadcast labelings of G is called the broadcast domination number γ b ( G ) of G . In this paper, we give bounds to the broadcast domination number of lexicographic product G H of a connected graph G and a graph H, and we show that the bounds are tight by determining the exact values for lexicographic products of some classes of graphs. Also, we give an algorithm which produces a dominating broadcast labeling of G H . We use the algorithm to find γ b ( P m H ) and γ b ( C m H ) . Further, we give an upper bound for the broadcast domination number of the modular product of two connected graphs and exact values are determined for the modular product of two graphs involving path, cycle and complete graphs.