Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: New Bounds for Codes Identifying Vertices in Graphs. | New Bounds for Codes Identifying Vertices in Graphs Gérard Cohen cohen@ Antoine Lobstein lobstein@ Iiro Honkala honkala@ i Gilles Zémor zemor@ Abstract Let G V E be an undirected graph. Let C be a subset of vertices that we shall call a code. For any vertex v 2 V the neighbouring set N V C is the set of vertices of C at distance at most one from v. We say that the code C identifies the vertices of G if the neighbouring sets N V CC V 2 V are all nonempty and di erent. What is the smallest size of an identifying code C We focus on the case when G is the two-dimensional square lattice and improve previous upper and lower bounds on the minimum size of such a code. AMS subject classification 05C70 68R10 94B99 94C12. Submitted February 12 1999 Accepted March 15 1999. G. Cohen A. Lobstein and G. Zemor are with ENST and CNRS URA 820 Computer Science and Network Dept. Paris France I. Honkala is with Turku University Mathematics Dept. Turku Finland THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R19 2 1 Introduction In this paper we investigate a problem initiated in 3 given an undirected graph G V E we define B v the ball of radius one centered at a vertex v 2 V by B v x 2 V d x v 1 where d x v represents the number of edges in a shortest path between v and x. The vertex v is then said to cover all the elements of B v . We often refer to a distinguished subset C of V as a code and to its elements as codewords. A code C is called a covering if the sets B v n C v 2 V are all nonempty if furthermore they are all different C is called an identifying code. The set of codewords covering a vertex v is called the identifying set I-set of v. Now what is the minimum cardinality of an identifying code This problem originates in 3 and is also taken up in 1 . Let us mention an application. A processor network can be modeled by an undirected graph G V E where V is the set of processors and E the set of their links. A selected subset C of the .
