Ville Junnila ; Tero Laihonen ; Tuomo Lehtilä ; María Luz Puertas - On Stronger Types of Locating-dominating Codes

dmtcs:4771 - Discrete Mathematics & Theoretical Computer Science, May 11, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-1
On Stronger Types of Locating-dominating CodesArticle

Authors: Ville Junnila ; Tero Laihonen ORCID; Tuomo Lehtilä ORCID; María Luz Puertas

    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.


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: May 11, 2019
    Accepted on: March 25, 2019
    Submitted on: August 22, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 663 times.
    This article's PDF has been downloaded 282 times.