## Abstract

Let G be a graph and S ⊆ V (G). For each vertex u ∈ S and for each v ∈ V (G) - S, we define over(d, -) (u, v) = over(d, -) (v, u) to be the length of a shortest path in 〈 V (G) - (S - {u}) 〉 if such a path exists, and ∞ otherwise. Let v ∈ V (G). We define w_{S} (v) = ∑_{u ∈ S} frac(1, 2^{over(d, -) (u, v) - 1}) if v / ∈ S, and w_{S} (v) = 2 if v ∈ S. If, for each v ∈ V (G), we have w_{S} (v) ≥ 1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γ_{e} (G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γ_{e} (G) ≥ (d + 2) / 4, and, (ii) that if G is a connected graph of order n, then γ_{e} (G) ≤ frac(2, 5) (n + 2).

Original language | English |
---|---|

Pages (from-to) | 5877-5883 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 19 |

DOIs | |

Publication status | Published - 6 Oct 2009 |

Externally published | Yes |

## Keywords

- Distance
- Domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics