An outer connected dominating(OCD) set of a graph $G=(V,E)$ is a set $\tilde{D} \subseteq V$ such that every vertex not in $S$ is adjacent to a vertex in $S$, and the induced subgraph of $G$ by $V \setminus \tilde{D}$, i.e. $G [V \setminus \tilde{D}]$, is connected. The OCD number of $G$ is the smallest cardinality of an OCD set of $G$. The outer-connected bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with a larger OCD number. Also, the outer-connected reinforcement number of G is the smallest number of edges whose addition to G results in a graph with a smaller OCD number. In 2018, Hashemi et al. demonstrated that the decision problems for the Outer-Connected Bondage and the Outer-Connected Reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results and show their hardness for bipartite graphs. Also, we obtain bounds for the outer-connected bondage number.
Hashemipour, M., Hooshmandasl, M. & Shakiba, A. (2019). On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity. Journal of Algorithms and Computation, 51(2), 63-74. https://doi.org/10.22059/jac.2019.75163
MLA
Hashemipour, M., Hooshmandasl, M., & Shakiba, A. "On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity", Journal of Algorithms and Computation, 51, 2, 2019, 63-74. doi: 10.22059/jac.2019.75163
HARVARD
Hashemipour M., Hooshmandasl M., Shakiba A. (2019). 'On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity', Journal of Algorithms and Computation, 51(2), pp. 63-74. doi: 10.22059/jac.2019.75163
CHICAGO
M. Hashemipour, M. Hooshmandasl & A. Shakiba, "On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity," Journal of Algorithms and Computation, 51 2 (2019): 63-74, doi: 10.22059/jac.2019.75163
VANCOUVER
Hashemipour M., Hooshmandasl M., Shakiba A. On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity. J. Algo. Comp. 2019;51(2):63-74. doi: 10.22059/jac.2019.75163
