On the complexity of locating-total domination in bipartite graphs

A total dominating set of a graph G = (V, E) with no isolated vertex is a set D ⊆ V (G) such that every vertex 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 V − D, N(u) ∩ D ≠ N(v) ∩ D. Let γtL(G) be the minimum cardinality of a locating-total dominating set of G. We show that the decision problem for locating-total domination number is NP-complete for bipartite graphs. We thus answer some open problems in [M. Miller, R. R. (2017). A not on locating-total domination in graphs. Discussiones Math. Graph Theory, 383-392].

کلیدواژه ها:

NP-complete Problems ، Locating-total Dominating Set ، Bipartite Graphs.