论文标题
分离株在图中的算法复杂性
Algorithmic Complexity of Isolate Secure Domination in Graphs
论文作者
论文摘要
如果诱发子图$ g [s] $至少具有一个孤立的顶点，则统治集合$ s $是一个孤立统治集（IDS）。在本文中，我们启动了称为“孤立安全统治”的新统治参数的研究。一个孤立统治集合$ s \ subseteq v $是一个孤立的安全主导集（ISD），如果对于每个顶点$ u \ in v \ setminus s $中的每个顶点$ u \，则存在一个相邻的$ v $ in $ s $中的$ u $ u $ in $ s $（s \ setMinus \ setMinus \ \ \ \ \ {v \} $ and iad $ $ g $的ISD的最小基数称为孤立的安全统治号码，并用$γ_{0s}（g）$表示。给定图形$ g =（v，e）$和一个正整数$ k，$ $ g $是检查$ g $是否具有孤立的安全主导尺寸，最多为$ k。$ $我们证明，即使在二级图形和拆分图中，即使限制了iSDM也是NP的np-Complete。我们还表明，ISDM可以在线性时间内求解，以用于界图的图形。
A dominating set $S$ is an Isolate Dominating Set (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set $S\subseteq V$ is an isolate secure dominating set (ISDS), if for each vertex $u \in V \setminus S$, there exists a neighboring vertex $v$ of $u$ in $S$ such that $(S \setminus \{v\}) \cup \{u\}$ is an IDS of $G$. The minimum cardinality of an ISDS of $G$ is called as an isolate secure domination number, and is denoted by $γ_{0s}(G)$. Given a graph $ G=(V,E)$ and a positive integer $ k,$ the ISDM problem is to check whether $ G $ has an isolate secure dominating set of size at most $ k.$ We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.
