An Efficient Algorithm to Find Minimum Extended Dominating Set in Cactus Graphs: Application In Wireless Sensor Networks

In a graph G and a positive integer k, a vertex set S, a subset of V is referred as a k-extended dominating set of G if for each vertex u of V , either the distance between u and at least one member of S is maximum one or there exist minimum k distinct vertices v1, v2, ...vk ∈ S such that u is situated exactly two distances from each vertex vi, i = 1, 2, ...k. The minimum number of elements among all minimum k-extended dominating sets of a graph G is termed as the k-extended domination number, denoted by γk(G). When k = 2, the set is known as an extended dominating set, and the corresponding minimum size is the extended domination number. A subset S of V (G) is called an extended connected dominating set if it is an extended dominating set and the subgraph induced by S is connected. In this article, we first study the concept of extended domination number and extended dominating sets specifically for cycle graphs. Using these results, we design an efficient algorithm that finds a minimum extended dominating set for cactus graphs in O(n) time. We also verify that our algorithm gives the correct output and analyze its time complexity. Finally, we show how our results can be applied to solve a real-world problem in a wireless sensor network using the idea of extended dominating sets.