Outer-weakly convex domination number of graphs

Abstract

For a given simple graph $G=(V,E)$, a set $S\subseteq V$ is an outer-weakly convex dominating set if every vertex in $V\setminus S$ is adjacent to some vertex in $S$ and $V\setminus S$ is a weakly convex set. The \emph{outer-weakly convex domination number} of a graph $G$, denoted by $\widetilde{\gamma}_{wcon}(G)$, is the minimum cardinality of an outer-weakly convex dominating set of $G$. %An outer-weakly convex dominating set of cardinality $\widetilde{\gamma}_{wcon}(G)$ will be called a $\widetilde{\gamma}_{wcon}$-$set$. In this paper, we initiate the study of outer-weakly convex domination as a new variant of graph domination and we show the close relationship that exists between this novel parameter and other domination parameters of a graph. Furthermore, we obtain general bounds on $\widetilde{\gamma}_{wcon}(G)$ and, for some particular families of graphs, we obtain closed formulae.

Keywords

• convex domination
• weakly-convex domination
• outer-connected domination
• outer-convex domination
• outer-weakly convex domination