2024/06/09 by Richard C. Brewster, Brewster, Richard C., Kiara A. McDonald +1
Computer Science · Engineering · #05C69 #05C70 #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2406.05825
openalex publication_date 2024/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Given a graph G=(V,E) of diameter d, a broadcast is a function f:V(G) → \ 0, 1, …, d \ where f(v) is at most the eccentricity of v. A vertex v is broadcasting if f(v)>0 and a vertex u hears v if d(u,v) ≤ f(v). A broadcast is independent if no broadcasting vertex hears another vertex and is a packing if no vertex hears more than one vertex. The weight of f is ∑v ∈ V f(v). We find the maximum weight independent and packing broadcasts for perfect k-ary trees, spiders, and double spiders as a partial answer to a question posed by Ahmane et al.