The minimum density of an identifying code in the king lattice

被引：37

作者：

Charon, I

Honkala, I

Hudry, O

Lobstein, A

机构：

[1] CNRS, F-75634 Paris 13, France

[2] ENST, F-75634 Paris 13, France

[3] Univ Turku, Dept Math, Turku 20014, Finland

来源：

DISCRETE MATHEMATICS | 2004年 / 276卷 / 1-3期

关键词：

graph theory; identifying codes;

D O I：

10.1016/S0012-365X(03)00306-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Consider a connected undirected graph G =(V, E) and a subset of vertices C. If for all vertices v is an element of V, the sets B-r(v) boolean AND C are all nonempty and different, where B-r(v) denotes the set of all points within distance r from v, then we call C an r-identifying code. For all r, we give the exact value of the best possible density of an r-identifying code in the king lattice, i.e., the infinite two-dimensional square lattice with two diagonals. (C) 2003 Published by Elsevier B.V.

引用

页码：95 / 109

页数：15

共 14 条

[1]

Blass U, 2000, J COMB DES, V8, P151, DOI 10.1002/(SICI)1520-6610(2000)8:2<151::AID-JCD8>3.0.CO

[2]

2-S

[3] Bounds on identifying codes [J].

Blass, U ;

Honkala, I ;

Litsyn, S .

DISCRETE MATHEMATICS, 2001, 241 (1-3) :119-128

[4]

Charon I., 2001, ELECTRON J COMB, V8, pR39

[5]

Charon I, 2002, ELECTRON J COMB, V9

[6]

Cohen G., 1999, ELECTRON J COMB, V6, pR19

[7]

Cohen G., 1999, ASPECTS ALGORITHMIQU, P19

[8]

Cohen G. D., 2001, Codes and Association Scheme. DIMACS Workshop. (Series in Discrete Mathematics and Theoretical Computer Science Vol.56), P97

[9] Bounds for codes identifying vertices in the hexagonal grid [J].

Cohen, GD ;

Honkala, I ;

Lobstein, A ;

Zémor, G .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (04) :492-504

[10] On codes identifying vertices in the two-dimensional square lattice with diagonals [J].

Cohen, GD ;

Honkala, I ;

Lobstein, A ;

Zémor, G .

IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (02) :174-176

← 1 2 →