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.