Portal de Periódicos da CAPES

Liar’s domination in graphs: Complexity and algorithm

2013; Elsevier BV; Volume: 161; Issue: 7-8 Linguagem: Inglês

10.1016/j.dam.2012.12.011

1872-6771

B. S. Panda, Sudipta Paul,

Interconnection Networks and Systems

A set L⊆V(G) of a graph G=(V,E) is a liar's dominating set if (1) for all v∈V(G), |NG[v]∩L|≥2 and (2) for every pair u,v∈V(G) of distinct vertices, |(NG[u]∪NG[v])∩L|≥3. A graph G=(V,E) admits a liar's dominating set if each of its connected component has at least three vertices. Given a graph G=(V,E) and an integer K, the liar's domination decision problem (LR-DOMDP) is to decide whether G has a liar's dominating set of cardinality at most K. Slater [P.J. Slater, Liar's Domination, Networks, 54(2) (2009) 70–74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar's domination in graphs, Discrete Math., 309(19) (2009) 5884–5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar's dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar's dominating set in a tree.