Watching systems in graphs: An extension of identifying codes

被引：12

作者：

Auger, David

Charon, Irene

Hudry, Olivier

Lobstein, Antoine ^{[1
]}

机构：

[1] Telecom ParisTech, Inst Telecom, F-75634 Paris 13, France

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 12期

关键词：

Graph theory; Complexity; Identifying codes; Watching systems; Paths; Cycles; DISCRIMINATING CODES; PLANAR GRAPHS; VERTICES; CYCLES; IDENTIFICATION; COMPLEXITY; SETS;

D O I：

10.1016/j.dam.2011.04.025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2011 Elsevier B.V. All rights reserved.

引用

页码：1674 / 1685

页数：12

共 27 条

[1]

[Anonymous], COMPLEXITE ALGORITHM

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3]

Auger D., 2010, 2010D011 INT TEL PAR, P40

[4] Complexity results for identifying codes in planar graphs [J].

Auger, David ;

Charon, Irene ;

Hudry, Olivier ;

Lobstein, Antoine .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (06) :691-710

[5]

Berge C., 1983, Graphes

[6] Identifying and locating-dominating codes on chains and cycles [J].

Bertrand, N ;

Charon, I ;

Hudry, O ;

Lobstein, A .

EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (07) :969-987

[7]

Bondy J.A., 2008, GTM

[8]

CHARBIT E, 2006, ELECT NOTES DISCRETE, V26, P29

[9] DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY [J].

Charbit, Emmanuel ;

Charon, Irene ;

Cohen, Gerard ;

Hudry, Olivier ;

Lobstein, Antoine .

ADVANCES IN MATHEMATICS OF COMMUNICATIONS, 2008, 2 (04) :403-420

[10]

Charon I., 2003, 2003D006 INT TEL PAR, P18

← 1 2 3 →