On Stronger Types of Locating-dominating Codes

zbMATH Open1411.05243arXiv1808.06891MaRDI QIDQ5377220FDOQ5377220

M. L. Puertas, Tuomo Lehtilä, Tero Laihonen, Ville Junnila

Publication date: 23 May 2019

Abstract: Locating-dominating codes in a graph find their application in sensor networks and have been studied extensively over the years. A locating-dominating code can locate one object in a sensor network, but if there is more than one object, it may lead to false conclusions. In this paper, we consider stronger types of locating-dominating codes which can locate one object and detect if there are multiple objects. We study the properties of these codes and provide bounds on the smallest possible size of these codes, for example, with the aid of the Dilworth number and Sperner families. Moreover, these codes are studied in trees and Cartesian products of graphs. We also give the complete realization theorems for the coexistence of the smallest possible size of these codes and the optimal locating-dominating codes in a graph.

Full work available at URL: https://arxiv.org/abs/1808.06891

Recommendations

zbMATH Keywords

dominating set locating-dominating set locating-dominating code Dilworth number Sperner's theorem

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (3)

This page was built for publication: On Stronger Types of Locating-dominating Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377220)