Identifying Codes with Small Radius in Some Infinite Regular Graphs
Open Access
- 1 January 2002
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 9 (1) , R11
Abstract
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$.
Keywords
This publication has 6 references indexed in Scilit:
- The minimum density of an identifying code in the king latticeDiscrete Mathematics, 2004
- On the Density of Identifying Codes in the Square LatticeJournal of Combinatorial Theory, Series B, 2002
- The noising methods: A generalization of some metaheuristicsEuropean Journal of Operational Research, 2001
- General Bounds for Identifying Codes in Some Infinite Regular GraphsThe Electronic Journal of Combinatorics, 2001
- New Bounds for Codes Identifying Vertices in GraphsThe Electronic Journal of Combinatorics, 1999
- On a new class of codes for identifying vertices in graphsIEEE Transactions on Information Theory, 1998