Algorithm complexity of neighborhood total domination and (ρ, γnt )-graphs
Algorithm complexity of neighborhood total domination and (ρ, γnt )-graphs
复制标题
邻域总支配的算法复杂度和 (α, βnt ) 图
DOI：
10.1007/s10878-017-0181-6
复制
发表时间：
--
影响因子：
1
通讯作者：
Kan Wang
中科院分区：
文献类型：
--
作者：
Changhong Lu;Bing Wang;Kan Wang
邻域总支配集，缩写为 NTD-setD，是 G 的顶点集，使得 D 是一个具有额外属性的支配集：由 D 的开邻域导出的子图没有孤立顶点。邻域总支配数（由 表示）是 G 中 NTD 集的最小基数。在本文中，我们证明 NTD 问题对于二分图和分裂图是 NP 完全的。然后我们给出一个线性时间算法来确定给定的树T。最后，我们描述了树的构造性属性，并提供了图的构造性特征，其中分别是给定图的支配数和包装数。
A neighborhood total dominating set, abbreviated for NTD-setD, is a vertex set ofGsuch thatDis a dominating set with an extra property: the subgraph induced by the open neighborhood ofDhas no isolated vertex. The neighborhood total domination number, denoted by, is the minimum cardinality of a NTD-set inG. In this paper, we prove that NTD problem is NP-complete for bipartite graphs and split graphs. Then we give a linear-time algorithm to determinefor a given treeT. Finally, we characterize a constructive property of-trees and provide a constructive characterization for-graphs, whereandare domination number and packing number for the given graph, respectively.