2017/08/17 by L. Gemmrich, Gemmrich, L., Christina M. Mynhardt +1
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1708.05455
openalex publication_date 2017/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A dominating broadcast on a graph G with vertex set V is a function f that maps V to 0,1,...,diam(G) such that f(v) does not exceed e(v) (the eccentricity of v) for all vertices v, and each vertex u is at distance at most f(v) from a vertex v with positive f(v). The upper broadcast domination number of G is Γb(G), which equals the maximum of the sum of the function values f(v), the maximum being taken over all minimal dominating broadcasts f on G. As shown by Erwin in [D. Erwin, Cost domination in graphs, Doctoral dissertation, Western Michigan University, 2001], Γb(G) is bounded below by diam(G) for any graph G. We investigate trees whose upper broadcast domination number equal their diameter and, among more general results, characterize caterpillars with this property.