On the Total Outer <i>k</i>-Independent Domination Number of Graphs

Abstract

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.

Keywords

• total outer k-independent domination
• total domination
• k-independence