论文标题
在图中安全连接支配的算法复杂性
Algorithmic Complexity of Secure Connected Domination in Graphs
论文作者
论文摘要
令$ g =（v，e）$为一个简单，无向和连接的图。连接的（总）支配集合$ s \ subseteq v $是$ g $的安全连接（总）支配集合，如果对于v \ setminus s $中的每个$ u \，则$ v \在s $中存在$ v \ in E $中的$ uv \ in E $ and $ and $（s \ setminus \ lbrace v \ lbrace as a rbrace） $ g $的主导集。 $γ_{sc}（g）（γ_{st}（g））$表示的安全连接（总）$ g $的$ g $的最小基数称为$ g $的安全连接（总）支配数。在本文中，我们表明，即使仅限于拆分图或两部分图，也对应于安全连接的支配数字和安全的总统治号码的决策问题也是NP的。 NP完全减少还表明这些问题是W [2] -HARD。我们还证明，安全连接的统治问题是可在块图和阈值图中溶解的线性时间。
Let $G = (V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $S \subseteq V$ is a secure connected (total) dominating set of $G$, if for each $ u \in V \setminus S$, there exists $v \in S$ such that $uv \in E$ and $(S \setminus \lbrace v \rbrace) \cup \lbrace u \rbrace $ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (total) dominating set of $G$ denoted by $ γ_{sc} (G) (γ_{st}(G))$, is called the secure connected (total) domination number of $G$. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs.
