×

Possible cardinalities for identifying codes in graphs. (English) Zbl 1114.94021

For a connected graph \(G(V, E)\), a subset \(C\) of the vertex set \(V\), and a positive integer \(r\), denote by \(B(r, v)\) the set of all vertices linked to a vertex \(v\) in \(V\) by a path of at most \(r\) edges called the ball of radius \(r\) centered at \(v\). If for all vertices \(v\) in \(V\), the intersection of the sets \(B(r, v)\) and \(C\) are all nonempty and different, then the set \(C\) is said to be an \(r\)-identifying code. It is known that the cardinality of a minimum \(r\)-identifying code in any connected graph \(G\) having a given number \(n\) of vertices lies in the interval \([\log(n+1), n-1]\), and that the values \(\log(n+1)\) and \(n-1\) can be achieved, where log is base 2. The purpose of this paper is to show that any in-between value can also be reached.

MSC:

94B35 Decoding
05C90 Applications of graph theory
94C12 Fault detection; testing in circuits and networks
94B60 Other types of codes
PDFBibTeX XMLCite