tailieunhanh - Báo cáo toán hoc:"A New Lower Bound on the Density of Vertex Identifying Codes for the Infinit"

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í toán học quốc tế đề tài: A New Lower Bound on the Density of Vertex Identifying Codes for the Infinit. | A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid Daniel W. Cranston Gexin yN Submitted Jul 20 2009 Accepted Sep 12 2009 Published Sep 18 2009 Mathematics Subject Classification 05C35 05C69 05C90 Abstract Given a graph G an identifying code DC V G is a vertex set such that for any two distinct vertices V1 v2 E V G the sets N v1 n D and N v2 n D are distinct and nonempty here N v denotes a vertex V and its neighbors . We study the case when G is the infinite hexagonal grid H. Cohen . constructed two identifying codes for H with density 3 7 and proved that any identifying code for H must have density at least 16 39 w . Both their upper and lower bounds were best known until now. Here we prove a lower bound of 12 29 w . 1 Introduction Identifying codes were introduced by Karpovsky et al. 6 in 1998 to model fault diagnosis in multiprocessor systems. If we model a multiprocessor as an undirected simple graph G then an r Ế -ID code is a subset of the vertices of G having the property that every collection of at most I vertices has a non-empty and distinct set of code vertices that are distance at most r from it. To be precise let Nr X be the set of vertices that are within distance r of X called the closed r-neighborhood . An r -ID code is a subset D of V G such that Nr X n D and Nr Y n D are distinct and non-empty for all distinct subsets X C V G and Y C V G with X Y Ế. In this paper we consider the case r 1 which we denote simply as Ế-ID codes we also write N v for N1 v . Not every graph has an GID code. For example if G contains two vertices u and v such that N u N v then G cannot have even a 1-ID code since for any subset of vertices D we have N u n D N v n D. However if for every pair of subsets X Y Department of Mathematics Applied Mathematics Virginia Commonwealth University Richmond VA 23284 Center for Discrete Mathematics and Theoretical Computer Science Rutgers Piscataway NJ 08854. Email .