تقرير
On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
| العنوان: | On the complexity of the outer-connected bondage and the outer-connected reinforcement problems |
|---|---|
| المؤلفون: | Hashemipour, M., Hooshmandasl, M. R., Shakiba, A. |
| سنة النشر: | 2018 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Computer Science - Computational Complexity, Mathematics - Combinatorics |
| الوصف: | 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$ of a graph $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}]$, the induced subgraph of $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{NP}$-hard. Also, the exact values of the bondage number are determined for several classes of graphs. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1802.00649 |
| رقم الأكسشن: | edsarx.1802.00649 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |