کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777036 | 1413649 | 2017 | 10 صفحه PDF | دانلود رایگان |
As a natural variant of domination in graphs, Dankelmann et al. (2009) introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if S is a set of vertices of a graph G, then S is an exponential dominating set of G if âvâS12dist(G,S)(u,v)â1â¥1 for every vertex u in V(G)âS, where dist(G,S)(u,v) is the distance between uâV(G)âS and vâS in the graph Gâ(Sâ{v}). The exponential domination number γe(G) of G is the minimum order of an exponential dominating set of G.Dankelmann et al. show 14(d+2)â¤Î³e(G)â¤25(n+2)for a connected graph G of order n and diameter d. We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph G of order n, maximum degree Î at least 3, and radius r, we show γe(G)â¥n13(Îâ1)2log2(Îâ1)+1log22(Îâ1)+log2(Îâ1)+1,γe(G)â¤22râ2, and γe(G)â¤43108(n+2).
Journal: Discrete Mathematics - Volume 340, Issue 3, March 2017, Pages 494-503