<![CDATA[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. ]]>
Copyrights © 2025
