## 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$$.

### 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
Full Text: