Generalized Weakly Connected Domination in Graphs

Abstract

A weakly connected dominating set $W$ of a graph $G$ is a dominating set such that the subgraph consisting of $V(G)$ and all edges incident on vertices in $W$ is connected. In this paper, we generalize it to $[r,R]$-dominating set which means a distance $r$-dominating set that can be connected by adding paths with length within $R$. We present an algorithm for finding $[r,R]$-dominating set with performance ratio not exceeding $ln{\mathrm{\Delta }}_r+\lceil \frac{2r+1}{R}\rceil –1$, where ${\mathrm{\Delta }}_r$ is the maximum number of vertices that are at distance at most $r$ from a vertex in the graph. The bound for size of minimum $[r,R]$-dominating set is also obtained.