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 \Delta_r + \lceil \frac{2r+1}{R}\rceil – 1\), where \(\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.