Identifying and locating-dominating codes on chains and cycles

Nathalie Bertrand; Irène Charon; Olivier Hudry; Antoine Lobstein

doi:10.1016/j.ejc.2003.12.013

Identifying and locating-dominating codes on chains and cycles

Nathalie Bertrand
, Irène Charon
, Olivier Hudry
, Antoine Lobstein

ENS Paris-Saclay
Telecom Paris

Research output: Contribution to journal › Article › peer-review

Abstract

Consider a connected undirected graph G=(V,E), a subset of vertices C⊆V, and an integer r≥1; for any vertex v∈V, let B_r(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v. If for all vertices v∈V (respectively, v∈V \C), the sets B_r(v)∩C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the smallest cardinalities or densities of these codes in chains (finite or infinite) and cycles.

Original language	English
Pages (from-to)	969-987
Number of pages	19
Journal	European Journal of Combinatorics
Volume	25
Issue number	7
DOIs	https://doi.org/10.1016/j.ejc.2003.12.013
Publication status	Published - 1 Oct 2004

Access to Document

10.1016/j.ejc.2003.12.013

Cite this

@article{9c3780543d274c9797c502ab7a3283f0,

title = "Identifying and locating-dominating codes on chains and cycles",

abstract = "Consider a connected undirected graph G=(V,E), a subset of vertices C⊆V, and an integer r≥1; for any vertex v∈V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v. If for all vertices v∈V (respectively, v∈V \textbackslash{}C), the sets Br(v)∩C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the smallest cardinalities or densities of these codes in chains (finite or infinite) and cycles.",

author = "Nathalie Bertrand and Ir{\`e}ne Charon and Olivier Hudry and Antoine Lobstein",

year = "2004",

month = oct,

day = "1",

doi = "10.1016/j.ejc.2003.12.013",

language = "English",

volume = "25",

pages = "969--987",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

number = "7",

}

TY - JOUR

T1 - Identifying and locating-dominating codes on chains and cycles

AU - Bertrand, Nathalie

AU - Charon, Irène

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2004/10/1

Y1 - 2004/10/1

N2 - Consider a connected undirected graph G=(V,E), a subset of vertices C⊆V, and an integer r≥1; for any vertex v∈V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v. If for all vertices v∈V (respectively, v∈V \C), the sets Br(v)∩C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the smallest cardinalities or densities of these codes in chains (finite or infinite) and cycles.

AB - Consider a connected undirected graph G=(V,E), a subset of vertices C⊆V, and an integer r≥1; for any vertex v∈V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v. If for all vertices v∈V (respectively, v∈V \C), the sets Br(v)∩C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the smallest cardinalities or densities of these codes in chains (finite or infinite) and cycles.

U2 - 10.1016/j.ejc.2003.12.013

DO - 10.1016/j.ejc.2003.12.013

M3 - Article

AN - SCOPUS:4344585685

SN - 0195-6698

VL - 25

SP - 969

EP - 987

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 7

ER -

Identifying and locating-dominating codes on chains and cycles

Abstract

Access to Document

Fingerprint

Cite this