On the complexity of the outer-connected bondage and the outer-connected reinforcement problems

Let $G=(V,E)$ be a graph. A subset $S\subseteq V$ is a dominating set of $G$ if every vertex not in $S$ is adjacent to a vertex in $S$. A set $\tilde{D} \subseteq V$ofagraph$G=(V,E) $ is called an outer-connected dominating set for $G$ if (1) $\tilde{D}$ is a dominating set for $G$, and (2) $G [V \setminus \tilde{D}]$,theinducedsubgraphof$G$by$V \setminus \tilde{D}$, is connected. The minimum size among all outer-connected dominating sets of $G$ is called the outer-connected domination number of $G$ and is denoted by ${\tilde{\gamma }}_c(G)$. We define the outer-connected bondage number of a graph $G$ as the minimum number of edges whose removal from $G$ results in a graph with an outer-connected domination number larger than the one for $G$. Also, the outer-connected reinforcement number of a graph $G$ is defined as the minimum number of edges whose addition to $G$ results in a graph with an outer-connected domination number, which is smaller than the one for $G$. This paper shows that the decision problems for the outer-connected bondage and the outer-connected reinforcement numbers are $\mathbf{N}\mathbf{P}$-hard. Also, the exact values of the bondage number are determined for several classes of graphs.