On the broadcast domination number of permutation graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2019 Elsevier B.V. Broadcast domination models the idea of covering a network of cities by transmitters of varying powers while minimizing the total cost of the transmitters used to achieve full coverage. To be exact, let G be a connected graph of order at least two with vertex set V(G) and edge set E(G). Let d(x,y), e(v), and diam(G), respectively, denote the length of a shortest xy path in G, the eccentricity of a vertex v in G, and the diameter of G. A function f:V(G){0,1,,diam(G)} is called a broadcast if f(v)e(v) for each vV(G). A broadcast f is called a dominating broadcast of G if, for each vertex uV(G), there exists a vertex vV(G) such that f(v)>0 and d(u,v)f(v). The broadcast domination number, b (G), of G is the minimum of vV(G) f(v) over all dominating broadcasts f on G. Let G 1 and G 2 be two disjoint copies of a graph G, and let :V(G 1 )V(G 2 ) be a bijection. Then a permutation graph G =(V,E) has vertex set V=V(G 1 )V(G 2 ) and edge set E=E(G 1 )E(G 2 ){uv:v=(u)}. For a connected graph G of order at least two, we prove the sharp bounds 2 b (G )2 b (G); we give an example showing that there is no function h such that b (G)
