Article Preview
TopIntroduction
The merger of the locating and dominating requirements for a set of nodes on a network has led to a wealth of research activity in the last 20 years. The introduction of locating sets is generally attributed to Hakimi (1964), although Jordan (1869) and Hua (1962) both had earlier contributions. The origination of dominating sets is usually traced to Ore (1962). Combining the ideas of location and domination have led to a number of distinct problems including, locating-dominating sets (Colbourn, Slater, & Stewart, 1987; Slater 1987), identifying codes (Cohen, Honkala, Lobstein, & Zémor, 2001), open locating-dominating sets (Seo & Slater, 2010; Seo & Slater, 2011) and metric locating dominating sets (Henning & Oellermann, 2004).
The detection and location of anomalies in a network is of central concern in a wide variety of application arenas. In sensor applications, sensors are placed at particular node locations designed to detect and locate anomalies that arise in the network. One way to lower initial costs and long-term maintenance costs for a collection of sensors, is to minimize the number of sensors needed to appropriately monitor the network. Unfortunately, these location–domination problems are, in general, computationally intractable (Givens, Kincaid, Mao, & Yu, 2017; Sweigart, 2019). A finite, connected, simple graph G(V, E) with node set V and edge set E provides a convenient model of a network or physical space. Nodes represent locations or regions and edges represent connections or communication ranges between those locations. The edges are assumed to be of unit length unless otherwise noted.
The focus of this paper is open locating dominating (OLD) sets that allow non-uniform weights (sensor strengths). However, it is helpful to consider three related problems to understand the difference between OLD sets and other location domination problems. Let an open neighborhood of a node 
, 
, be the set of nodes adjacent to node v, excluding v. A closed neighborhood of a node v is denoted by 
and is the union of 
with v. Let 
denote a subset of nodes in a graph 
.
In (Seo & Slater, 2011) a set S is a Locating-Dominating (LD) set if every node not in S has at least one neighbor in S and there is no distinct pair of nodes not in S with the same set of neighbors in S. Hence, S is a LD set if both of the following conditions are met.