Maximum boundary independent broadcasts in graphs and trees - Hoepner, Julia Ingrid; MacGillivray, Gary; Mynhardt, Christina (Electronic Journal of Graph Theory and Applications (EJGTA), 2025)
A broadcast on a connected graph G is a function f : V(G)→{0, 1, ...,  diam(G)} such that f(v)≤e(v) (the eccentricity of v) for all v ∈ V. If dG(u, v)≥f(u)+f(v) for any pair of vertices u, v with f(u)>0 and f(v)>0, the broadcast is said to be boundary independent.We show that the maximum weight αbn(G) of a boundary independent broadcast can be bounded in terms of the independence number α(G), and prove that the maximum boundary independent broadcast problem is NP-hard. We investigate bounds on αbn(T) when T is a tree in terms of its order and the number of vertices of degree at least 3, and determine a sharp upper bound on αbn(T) when T is a caterpillar, giving αbn(T) exactly for certain families of caterpillars. We conclude by describing a polynomial-time algorithm to determine αbn(T) for a given tree T.