Broadcast Domination in Line Graphs of Trees

Abstract

A dominating broadcast of a graph G is a function f : V(G) → {0, 1, 2, . . ., diam(G)} such that f(v) ≼ e(v) for all v ∈ V(G), where e(v) is the eccentricity of v, and for every vertex u ∈ V(G), there exists a vertex v with f(v) > 0 and d(u, v) ≼ f(v). The cost of f is P<inf>v</inf>∈V(G<inf>)</inf> f(v). The minimum of costs over all the dominating broadcasts of G is called the broadcast domination number γ<inf>b</inf>(G) of G. A graph G is said to be radial if γ<inf>b</inf>(G) = rad(G). In this article, we give tight upper and lower bounds for the broadcast domination number of the line graph L(G) of G, in terms of γ<inf>b</inf>(G), and improve the upper bound of the same for the line graphs of trees. We present a necessary and sufficient condition for radial line graphs of central trees, and exhibit constructions of infinitely many central trees T for which L(T) is radial. We give a characterization for radial line graphs of trees, and show that the line graphs of the i-subdivision graph of K<inf>1,n</inf> and a subclass of caterpillars are radial. Also, we show that γ<inf>b</inf>(L(C)) = γ(L(C)) for any caterpillar C. © 2023 Charles Babbage Research Centre. All rights reserved.