Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: An optimal strongly identifying code in the infinite triangular grid. | An optimal strongly identifying code in the infinite triangular grid Iiro Honkala Department of Mathematics University of Turku 20014 Turku Finland honkala@ i Submitted Aug 18 2009 Accepted Jun 15 2010 Published Jun 29 2010 Mathematics Subject Classification 05C69 68R10 Abstract Assume that G V E is an undirected graph and C c V. For every v G V we denote by I v the set of all elements of C that are within distance one from v. If the sets I v v for v G V are all nonempty and moreover the sets I v I v v for v G V are disjoint then C is called a strongly identifying code. The smallest possible density of a strongly identifying code in the infinite triangular grid is shown to be 6 19. Keywords Graph identifying code triangular grid density. 1 Introduction Assume that G V E is an undirected graph with vertex set V and edge set E. A subset C c V is called a code in G and its elements are called codewords. The distance d u v between two vertices u and v is the number of edges on any shortest path between them. For all v G V we denote I v c G C d c v 1 . If we denote by Br v the ball of radius r with centre v then I v C n B1 v . If all the sets I v are nonempty and pairwise different then C is called an identifying code. This concept was introduced in 8 in connection with studying multiprocessor Research supported by the Academy of Finland under grant 210280. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R91 1 architectures. Such an architecture can be viewed as a graph where each vertex represents a processor and each edge represents a dedicated link between two processors. Assume that at most one of the processors is malfunctioning. Each of the chosen codewords c tests the sets B1 c and reports YES if it detects a problem and NO otherwise. The fact that C is identifying implies that based on the reports we can uniquely identify the one malfunctioning processor or tell that everything is fine. Strongly identifying codes were introduced in 7 in a more general form
