Broadcast Domination in Graphs and its Critical Aspects

Abstract

Adistance related domination parameter deals with the idea where a subset of vertices are at an acceptable distances from the rest of the vertices. In this context, a vertex can dominate other vertices beyond its neighbors. Broadcast domination is a distance related domination parameter of a graph which captures the true flavor of the idea of varying dominating ability of a vertex. A dominating broadcast of a graph G is a func tion f :V(G)→{0,1,2,...,diam(G)} such that f(v) is at most the eccentricity of v, for all v ∈V(G), and for every vertex u ∈V(G), there exists a vertex v with f(v) > 0 and d(u,v) ⩽ f(v). The cost σ(f) of f is ∑v∈V(G) f(v). The minimum of costs over all the dominating broadcasts of G is called the broadcast domination number γb(G) of G. A dominating broadcast f is referred as an optimal dominating broadcast if σ(f)=γb(G). In this thesis, we present a new tight upper bound involving the order and the minimum degree, and a new tight lower bound for the same concerning the order and the maxi mumdegreeofG. Weimprovedtheupper bound for the broadcast domination numbers of a subclass of regular graphs. Further, we study the broadcast domination number for the generalized Petersen graphs and a subclass of circulant graphs. After that, we study the broadcast domination number of a graph under some graph operations. We present upper bounds for the broadcast domination numbers of lexicographic and modular prod ucts of graphs, in term of the broadcast domination numbers of its factor graphs. An algorithm for finding a dominating broadcast for the lexicographic product of graphs is given, which also produces an optimal dominating broadcast for some graphs. Also, we determine the exact values of the broadcast domination numbers for those products of graphs concerning path, cycle and complete graphs. Next, we study the broadcast dom ination of line graphs. We prove that γb(G) 2 ⩽γb(L(G))⩽γb(G) and improve the upper bound of the same for the line graphs of trees. We present a necessary and sufficient condition for radial line graphs of central trees, and exhibit constructions of infinitely many central trees T for which L(T) is radial. We give a characterization for radial line graphs of trees, and discuss the broadcast domination numbers for line graphs of caterpillars and i-subdivision graph of K1,n. We instigate the study of critical aspects in broadcast domination with respect to edge deletion and edge addition. A graph G with i γb(G) = k is said to be k-γ+ b-edge-critical (k-γ− b-edge-critical) if γb(G −e) > γb(G), for every edge e ∈ E(G) (if γb(G+e) < γb(G), for every edge e ∈ E( G)). We give a necessary and sufficient condition for k-γ+ b-edge-critical graph. We characterize k-γ− b edge-critical graphs for k = 1,2, and give necessary conditions of the same for k ⩾ 3. Further, we introduce the concept of the broadcast bondage number and the broadcast reinforcement number of a graph, and give some sharp upper bounds for them.