2021/05/05 by Christina M. Mynhardt, Mynhardt, C. M., L. Neilson +1
Computer Science · Materials Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Graphene research and applications
paper · pdf · doi:10.48550/arxiv.2105.02312
openalex publication_date 2021/05/05 · openalex created_date 2021/05/10 · openalex updated_date 2026/07/28
A broadcast on a nontrivial connected graph G is a function f from V(G) to the set 0,1,...,diam(G) such that f(v) is at most the eccentricity of v for all vertices v of G. The weight of f is the sum of the function values over V(G). A vertex u hears f from v if f(v) is positive and u is within distance f(v) from v. A broadcast f is boundary independent if any vertex that hears f from two or more vertices is at distance f(v) from each such vertex v. The maximum weight of a boundary independent broadcast on G is denoted by αbn(G). We prove a sharp lower bound on αbn(T) for a tree T. Combined with a previously determined upper bound, this gives exact values of αbn(T) for some classes of trees T. We also determine αbn(T) for trees with exactly two branch vertices and use this result to demonstrate the existence of trees for which αbn lies strictly between the lower and upper bounds.