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

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\).


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
Full Text: EuDML EMIS