Double Outer-Independent Domination in Graphs

Abstract

We initiate the study of double outer-independent domination in graphs. A vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ is dominated by at least two vertices of $D$, and the set $V(G)\setminus D$ is independent. The double outer-independent domination number of a graph $G$ is the minimum cardinality of a double outer-independent dominating set of $G$. First, we discuss the basic properties of double outer-independent domination in graphs. We find the double outer-independent domination numbers for several classes of graphs. Next, we prove lower and upper bounds on the double outer-independent domination number of a graph, and we characterize the extremal graphs. Then, we study the influence of removing or adding vertices and edges. We also give Nordhaus-Gaddum type inequalities.