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

CNRS

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

16 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	1674-1685
Nombre de pages	12
journal	Discrete Applied Mathematics
Volume	161
Numéro de publication	12
Les DOIs	https://doi.org/10.1016/j.dam.2011.04.025
état	Publié - 1 août 2013

Accès au document

10.1016/j.dam.2011.04.025

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation