Watching systems in graphs: An extension of identifying codes

David Auger; Irène Charon; Olivier Hudry; Antoine Lobstein

doi:10.1016/j.dam.2011.04.025

Watching systems in graphs: An extension of identifying codes

David Auger
, Irène Charon
, Olivier Hudry
, Antoine Lobstein

Centre national de la recherche scientifique

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

16 Citations (Scopus)

Abstract

We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.

Original language	English
Pages (from-to)	1674-1685
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	161
Issue number	12
DOIs	https://doi.org/10.1016/j.dam.2011.04.025
Publication status	Published - 1 Aug 2013

Keywords

Complexity
Cycles
Graph theory
Identifying codes
Paths
Watching systems

Access to Document

10.1016/j.dam.2011.04.025

Cite this

@article{21c50a53eb3a40e5b02f3aa6eff824a7,

title = "Watching systems in graphs: An extension of identifying codes",

abstract = "We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.",

keywords = "Complexity, Cycles, Graph theory, Identifying codes, Paths, Watching systems",

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

year = "2013",

month = aug,

day = "1",

doi = "10.1016/j.dam.2011.04.025",

language = "English",

volume = "161",

pages = "1674--1685",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Watching systems in graphs

T2 - An extension of identifying codes

AU - Auger, David

AU - Charon, Irène

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2013/8/1

Y1 - 2013/8/1

N2 - We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.

AB - We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.

KW - Complexity

KW - Cycles

KW - Graph theory

KW - Identifying codes

KW - Paths

KW - Watching systems

U2 - 10.1016/j.dam.2011.04.025

DO - 10.1016/j.dam.2011.04.025

M3 - Article

AN - SCOPUS:84876664763

SN - 0166-218X

VL - 161

SP - 1674

EP - 1685

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 12

ER -

Watching systems in graphs: An extension of identifying codes

Abstract

Keywords

Access to Document

Fingerprint

Cite this