A unit disk graph is the intersection graph of a set of unit diameter disks in the plane. In this paper we consider liar's domination problem on unit disk graphs, a variant of dominating set problem. We call this problem as Euclidean liar's domination problem . In the Euclidean liar's domination problem, a set @math of @math points (disk centers) are given in the Euclidean plane. For @math , @math is a subset of @math such that for any @math , the Euclidean distance between @math and @math is less than or equal to 1, i.e., the corresponding unit diameter disks intersect. The objective of the Euclidean liar's domination problem is to find a subset @math of minimum size having the following properties : (i) @math for @math , and (ii) @math for @math . This article aims to prove the Euclidean liar's domination problem is NP-complete.
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. Assume that each vertex of a graph G is the possible location for an “intruder” such as a thief, or a saboteur, a fire in a facility or some possible processor fault in a computer network. A device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and to identify at which vertex in N[v] the intruder is located. One must then have a dominating set S ⊆ V(G), a set with ∪v∈SN[v] = V(G), to be able to identify any intruder's location. If any one device can fail to detect the intruder, then one needs a double-dominating set. This article introduces the study of liar's dominating sets, sets that can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location. Liar's dominating sets lie between double-dominating sets and triple-dominating sets because every triple-dominating set is a liar's dominating set, and every liar's dominating set must double dominate. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 