Shahed University
A note on the complexity of locating-total domination in graphs
H. Rahbani | Nader Jafari Rad | Mohammad-Reza Sadeghi
URL :
http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116896
Date :
2019/10/01
Publish in :
Theoretical Computer Science
DOI :
https://doi.org/https://doi.org/10.1016/j.tcs.2019.09.039
Link :
https://www.sciencedirect.com/science/article/pii/S0304397519306036
Keywords :
Locating-total domination; NP-complete
Abstract :
A total dominating set of a graph with no isolated vertex is a set such that every vertex of G is adjacent to a vertex in D. A total dominating set D of G is a locating-total dominating set if for every pair of distinct vertices u and v in , . Let be the minimum cardinality of a locating-total dominating set of G. In this paper, we show that the decision problem for locating-total domination number is NP-complete for several classes of graphs. In particular, we answer a problem posed in Discussiones Math. Graph Theory 37 3(2017), 745–754. We also define classes of graphs for which the complexities of domination number, locating domination number and locating-total domination number are different.
Authors' Home page
Nader Jafari Rad