2021/04/06 by Christina M. Mynhardt, Mynhardt, C. M., L. Neilson +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2104.02266
A broadcast on a nontrivial connected graph G with vertex set V is a function f from V to 0,1,...,diam(G) such that f(v) is at most the eccentricity of v for all vertices v. The weight of f is the sum of the function values taken over V. A vertex u hears f from v if f(v) is positive and d(u,v) is at most f(v). A broadcast f is boundary independent if, for any vertex w that hears f from vertices v1,...,vk, where k is at least 2, d(w,vi) equals f(vi) for each i. The maximum weight of a boundary independent broadcast on G is denoted by αbn(G). We prove a sharp upper bound on αbn(T) for a tree T in terms of its order and number of branch vertices of a certain type.