A note on bounds for the broadcast domination number of graphs

Abstract

A dominating broadcast 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 u∈V(G), there exists a vertex v with f(v)⩾1 and d(u,v)⩽f(v). The cost of f is ∑<inf>v∈V(G)</inf>f(v). The minimum cost over all the dominating broadcasts of G is called the broadcast domination number γ<inf>b</inf>(G) of G. In this paper, we give new upper and lower bounds for γ<inf>b</inf>(G). We show that both the bounds are tight. Also, we improve the upper bound for a subclass of regular graphs. Further, we explore the broadcast domination numbers of generalized Petersen graphs and a subclass of circulant graphs. © 2024 Elsevier B.V.