Algorithm complexity of neighborhood total domination and -graphs

作者：Lu, Changhong; Wang, Bing^*; Wang, Kan

来源：Journal of Combinatorial Optimization, 2018, 35(2): 424-435.

DOI：10.1007/s10878-017-0181-6

• Neighborhood total domination
• Algorithm complexity
• Labeled graph

A neighborhood total dominating set, abbreviated for NTD-set D, is a vertex set of G such that D is a dominating set with an extra property: the subgraph induced by the open neighborhood of D has no isolated vertex. The neighborhood total domination number, denoted by , is the minimum cardinality of a NTD-set in G. 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 determine for a given tree T. Finally, we characterize a constructive property of -trees and provide a constructive characterization for -graphs, where and are domination number and packing number for the given graph, respectively.

• 出版日期2018-2
• 单位华东师范大学