Identifying and locating-dominating codes on chains and cycles
type: Item
instance of: scholarly article
title: Identifying and locating-dominating codes on chains and cycles
zbMATH Open document ID: 1053.05095
author: Nathalie Bertrand
author: Irène Charon
author: Olivier Hudry
author: Antoine Lobstein
published in: European Journal of Combinatorics
publication date: 2004-10-13T00:00:00Z
review text: On a connected undirected graph \((V,E)\), an \(r\)-identifying code is a subset \(C\) of \(V\) such that the sets \(B_r(v)\cap C\) are distinct and nonempty for all \(v\in V\). A code is \(r\)-locating-dominating if this is true for all \(v\in V\backslash C\). This paper determines the minimum sizes (or densities) in many cases for these codes on finite and infinite chains and cycles.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 2107443
zbMATH Keywords: \(r\)-identifying code
zbMATH Keywords: \(r\)-locating-dominating code
reviewed by: Ki Hang Kim
MaRDI profile type: Publication
full work available at URL: j.ejc.2003.12.013
OpenAlex ID: W2037221311
cites work: Q4659582
cites work: The minimum density of an identifying code in the king lattice.
cites work: Identifying codes with small radius in some infinite regular graphs
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: Q3789614
cites work: Q5429563
cites work: On a new class of codes for identifying vertices in graphs
cites work: Q3803159
cites work: Q4871068
DOI: 10.1016/J.EJC.2003.12.013
Recommended article: Identifying codes and locating-dominating sets on paths and cycles
Recommended article: Q3090475
Recommended article: Q5442540
Recommended article: Approximability of identifying codes and locating-dominating codes
Recommended article: Identifying and locating-dominating codes: NP-completeness results for directed graphs
Recommended article: Locating-dominating codes in paths
Recommended article: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
Recommended article: Q4566243
Recommended article: Locating and identifying codes in circulant graphs
Recommended article: Identifying and Locating–Dominating Codes in (Random) Geometric Networks
description: scientific article; zbMATH DE number 2107443