Paper Info
Title
Liar's domination in graphs: Complexity and algorithm
Abstract
A set L@?V(G) of a graph G=(V,E) is a liar's dominating set if (1) for all v@?V(G), |N"G[v]@?L|=2 and (2) for every pair u,v@?V(G) of distinct vertices, |(N"G[u]@?N"G[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.
Year
DOI
Venue
2013
10.1016/j.dam.2012.12.011
Discrete Applied Mathematics
Keywords
Field
DocType
dominating set problem,algorithmic result,complexity result,bipartite graph,minimum cardinality liar,set l,graph g,chordal graph,p.j. slater,k. slater,np completeness
Integer,Discrete mathematics,Combinatorics,Dominating set,Vertex (geometry),Chordal graph,Bipartite graph,Algorithm,Cardinality,Connected component,Time complexity,Mathematics
Journal
Volume
Issue
ISSN
161
7-8
0166-218X
Citations 
PageRank 
References 
4
0.49
4
Authors
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
S. Paul240.49