Open Locating-Dominating Sets in Circulant Graphs

Givens, Robin M. ; Yu, Gexin ; Kincaid, Rex K.

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 47-62

Résumé

Location detection problems have been studied for a variety of applications including finding faults in multiprocessors, contaminants in public utilities, intruders in buildings and facilities, and for environmental monitoring using wireless sensor networks. In each of these applications, the system or structure can be modeled as a graph, and sensors placed strategically at a subset of vertices can locate and detect anomalies in the system. An open locating-dominating set (OLD-set) is a subset of vertices in a graph in which every vertex in the graph has a non-empty and unique set of neighbors in the subset. Sensors placed at OLD-set vertices can uniquely detect and locate disturbances in a system. These sensors can be expensive and, as a result, minimizing the size of the OLD-set is critical. Circulant graphs, a group of regular cyclic graphs, are often used to model parallel networks. We prove the optimal OLD-set size for a particular circulant graph using Hall’s Theorem. We also consider the mixed-weight OLD-set introduced in [R.M. Givens, R.K. Kincaid, W. Mao and G. Yu, Mixed-weight open locating-dominating sets, in: 2017 Annual Conference on Information Science and Systems, (IEEE, Baltimor, 2017) 1–6] which models a system with sensors of varying strengths. To model these systems, we place weights on the vertices in the graph, representing the strength of a sensor placed at the corresponding location in the system. We study particular mixed-weight OLD-sets in cycles, which behave similarly to OLD-sets in circulant graphs, and show the optimal mixed-weight OLD-set size using the discharging method.

Détail

Keywords: open locating-dominating sets, circulant graphs, Hall’s Matching Theorem, mixed-weight open locating-dominating sets