Name
Abstract | ||
|---|---|---|
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 ź S 1 2 dist ( 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 1 4 ( d + 2 ) ź γ e ( G ) ź 2 5 ( 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 ) ź n 13 ( Δ - 1 ) 2 log 2 ( Δ - 1 ) + 1 log 2 2 ( Δ - 1 ) + log 2 ( Δ - 1 ) + 1 , γ e ( G ) ź 2 2 r - 2 , źandź γ e ( G ) ź 43 108 ( n + 2 ) . |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.08.024 | Discrete Mathematics |
Keywords | Field | DocType |
Domination,Exponential domination | Discrete mathematics,Dominating set,Combinatorics,Exponential function,Vertex (geometry),Upper and lower bounds,Degree (graph theory),Domination analysis,Connectivity,Mathematics,Exponential growth | Journal |
Volume | Issue | ISSN |
340 | 3 | 0012-365X |
Citations | PageRank | References |
3 | 0.57 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Dieter Rautenbach | 3 | 946 | 138.87 |