Outer-2-independent domination; domination; outer-connected domination; Vizing’s conjecture; cartesian product of graphs.
We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph 𝐺 is a set 𝐷 of vertices of 𝐺 such that every vertex of 𝑉 (𝐺)\𝐷 has a neighbor in 𝐷 and the maximum vertex degree of the subgraph induced by 𝑉 (𝐺)\𝐷 is at most one. The outer-2-independent domination number of a graph 𝐺 is the minimum cardinality of an outer-2-independent dominating set of 𝐺. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.