Name
Abstract | ||
|---|---|---|
As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduced 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 Sigma(v is an element of 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 is an element of V (G) \ S and v is an element of S in the graph G - (S \ {v}). The exponential domination number gamma(e)(G) of G is the minimum order of an exponential dominating set of G.In the present paper we study exponential domination in subcubic graphs. Our results are as follows. If G is a connected subcubic graph of order n(G), thenn(G)/6 log(2)(n(G) + 2) + 4 <= gamma(e)(G) <= 1/3 (n(G) + 2).For every epsilon > 0, there is some g such that gamma(e)(G) <= epsilon n(G) for every cubic graph G of girth at least g. For every 0 < alpha < 2/3ln(2), there are infinitely many cubic graphs G with gamma(e)(G) <= 3n(G)/ln(n(G))(alpha). If T is a subcubic tree, then gamma(e)(T) >= 1/6 (n(T) + 2). For a given subcubic tree, gamma(e)(T) can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs. |
Year | Venue | Keywords |
|---|---|---|
2016 | ELECTRONIC JOURNAL OF COMBINATORICS | domination, exponential domination, subcubic graph, cubic graph, girth, cage |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Dominating set,Exponential function,Vertex (geometry),Cubic graph,Exponential decay,Domination analysis,Mathematics | Journal | 23 |
Issue | ISSN | Citations |
4 | 1077-8926 | 2 |
PageRank | References | Authors |
0.53 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Dieter Rautenbach | 3 | 946 | 138.87 |