2021/05/10 by Mynhardt, Kieka, Elise Marchessault, Marchessault, Elise
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2105.04611
openalex publication_date 2021/05/10 · openalex created_date 2021/05/24 · openalex updated_date 2026/07/28
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 Vf% + denote the set of vertices v such that f(v) is positive. A vertex u hears f from v∈ Vf+ 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 Vf+ also satisfies d(x,u)≥ f(u) for all u∈ Vf+, we say that the broadcast only overlaps in boundaries. A broadcast f is boundary independent if it overlaps only in boundaries. Denote by ibn(G) the minimum cost of a maximal boundary independent broadcast. We obtain a characterization of maximal boundary independent broadcasts, show that ibn(T′)≤ ibn(T) for any subtree T′ of a tree T, and determine an upper bound for ibn(T) in terms of the broadcast domination number of T. We show that this bound is sharp for an infinite class of trees.