CRITICAL ASPECTS IN BROADCAST DOMINATION

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) and [ v2V (G) f(v)>0 [{u ∈ V (G) : d(u, v) ≤ f(v)}] = V (G), where e(v) is the eccentricity of v. The cost of f is Σ v2V (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 introduce the critical aspects in broadcast domination and study it with respect to edge deletion and edge addition. A graph G 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)), where γb(G) = k. We give a necessary and sufficient condition for a graph to be k-γ+ b -edge-critical. We characterize k-γ- b -edge-critical graphs for k = 1, 2, and give necessary conditions of the same for k > 3. Further, we define the broadcast bondage number and the broadcast reinforcement number of a graph, and give tight upper bounds for them. © 2024 University of Zielona Gora. All rights reserved.