Critical aspects in broadcast domination

Sen, Jishnu  ; Kola, Srinivasa Rao

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1485-1512

Résumé

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 ⋃_v ∈ V(G) f(v) gt; 0 [ u ∈ V(G) : d(u,v) ≤ f(v) ]=V(G), where e(v) is the eccentricity of 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 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) gt; γ_b(G), for every edge e ∈ E(G) (if γ_b(G+e) lt; γ_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.

Détail

Keywords: dominating broadcast labeling, broadcast domination number, critical graph, bondage number, reinforcement number