A Linear Time Algorithm for Weighted k-Fair Domination Problem in Cactus Graphs

Abstract

A set D of vertices in a graph G is a k-fair dominating set if every vertex not in D is adjacent to exactly k vertices in D. The weighted k-fair domination number $\mathrm {wfd}_k(G)$ of a vertex-weighted graph G is the minimum weight w(D) among all k-fair dominating sets D. In addition to the weighted k-fair domination number, some auxiliary parameters are defined. It is shown that for a cactus graph, the weighted k-fair domination number and auxiliary parameters can be calculated in linear time.

Appendix

1.1 Auxiliary Algorithms

The following algorithms are in direct correspondence with Lemma 1, Lemma 3 and Lemma 4. First algorithm computes parameters values of the rooted path-like graph with s vertices. The second and the third also compute the parameters values of the rooted path-like graph but with the given condition (to be a member or not of the dominating set) on the last vertex in DFS order. The last algorithm computes the parameters values of the cycle-like graph with s vertices. The input of all these algorithms is parameters values for each vertex in path or in cycle. These values are either initial values (see (8)) or already computed parameters values of the proper sub-cacti (sub-cacti $G_1, G_2,\ldots ,G_s$ in Fig. 6 or in Fig. 7).