A set of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex in such a set. We say that a total dominating set D is a total outer k-independent dominating set of G if the maximum degree of the subgraph induced by the vertices that are not in D is less or equal to $k-1$ . The minimum cardinality among all total outer k-independent dominating sets is the total outer k-independent domination number of G. In this article, we introduce this parameter and begin with the study of its combinatorial and computational properties. For instance, we give several closed relationships between this novel parameter and other ones related to domination and independence in graphs. In addition, we give several Nordhaus–Gaddum type results. Finally, we prove that computing the total outer k-independent domination number of a graph G is an NP-hard problem.

A nonempty subset $D\subset V$ of vertices of a graph $G=(V,E)$ is a dominating set if every vertex of this graph is adjacent to at least one vertex from this set except the vertices which belong to this set itself. $D\subseteq V$ is a total k-dominating set if there are at least k vertices in set D adjacent to every vertex $v\in V$, and it is a global total k-dominating set if D is a total k-dominating set of both G and $\overline{G}$. The global total k-domination number of G, denoted by ${\gamma }_{kt}^g\left(G\right)$, is the minimum cardinality of a global total k-dominating set of G, GTkD-set. Here we derive upper and lower bounds of ${\gamma }_{kt}^g\left(G\right)$, and develop a method that generates a GTkD-set from a GT$(k-1)$D-set for the successively increasing values of k. Based on this method, we establish a relationship between ${\gamma }_{(k-1)t}^g\left(G\right)$ and ${\gamma }_{kt}^g\left(G\right)$, which, in turn, provides another upper bound on ${\gamma }_{kt}^g\left(G\right)$.

A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01.