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.