Identifying codes with small radius in some infinite regular graphs. (English) Zbl 0985.05033

Charon, Irène; Hudry, Olivier; Lobstein, Antoine

Electron. J. Comb. 9, No. 1, Research paper R11, 25 p. (2002); printed version J. Comb. 9, No. 1 (2002).

Summary: Let \(G=(V,E)\) be a connected undirected graph and \(S\) a subset of vertices. If for all vertices \(v \in V\), the sets \(B_r(v) \cap S\) are all nonempty and different, where \(B_r(v)\) denotes the set of all points within distance \(r\) from  \(v\), then we call \(S\) an \(r\)-identifying code. We give constructive upper bounds on the best possible density of \(r\)-identifying codes in four infinite regular graphs, for small values of \(r\).

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10	Graph theory (including graph drawing) in computer science
94B65	Bounds on codes

Keywords:

\(r\)-identifying code; infinite regular graphs