Lower boundary independent broadcasts in trees

Marchessault, E.M. ; Mynhardt, C.M. 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 75-99

Résumé

A broadcast on a connected graph G=(V,E) is a function f:V→{0,1, . . . , diam(G)} such that f(v)≤ e(v) (the eccentricity of v) for all v∈ V if |V|≥2, and f(v)=1 if V={v}. The cost of f is σ(f)=∑_v∈ Vf(v). Let V_f^+={v∈ V:f(v) gt;0}. A vertex u hears f from v∈ V_f^+ if the distance d(u,v)≤ f(v). When f is a broadcast such that every vertex x that hears f from more than one vertex in V_f^+ also satisfies d(x,u)≥ f(u) for all u∈ V_f^+, we say that the broadcast only overlaps in boundaries. A broadcast f is boundary independent if it overlaps only in boundaries. Denote by i_bn(G) the minimum cost of a maximal boundary independent broadcast. We obtain a characterization of maximal boundary independent broadcasts, show that i_bn(T^')≤ i_bn(T) for any subtree T^' of a tree T, and determine an upper bound for i_bn(T) in terms of the broadcast domination number of T. We show that this bound is sharp for an infinite class of trees.

Détail

Keywords: broadcast domination, broadcast independence, boundary independence