2016/12/25 by Messaouda Ahmane, Ahmane, Messaouda, Isma Bouchemakh +3 · 1 citation
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1612.08283
arxiv created 2018/01/16 · arxiv updated 2018/01/17
Let G be a simple undirected graph.A broadcast on G isa function f : V(G)→ℕ such that f(v)≤ e_G(v) holds for every vertex v of G, where e_G(v) denotes the eccentricity of v in G, that is, the maximum distance from v to any other vertex of G.The cost of f is the value \rm cost(f)=∑_v∈ V(G)f(v).A broadcast f on G is independent if for every two distinct vertices u and v in G, d_G(u,v)>max\f(u),f(v)\,where d_G(u,v) denotes the distance between u and v in G.The broadcast independence number of G is then defined as the maximum cost of an independent broadcast on G. In this paper, we study independent broadcasts of caterpillars and give an explicit formula for the broadcast independence number of caterpillars having no pair of adjacent vertices with degree 2.