Domination and location in acyclic graphs

Abstract Locating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V ‐ S is adjacent to at least one vertex in S. For each v in V ‐ S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V ‐ S one has S(v) ≠ S(w) . Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating‐dominating set in an acyclic graph is presented.