کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419368 | 683793 | 2013 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New bounds on the minimum density of an identifying code for the infinite hexagonal grid
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: New bounds on the minimum density of an identifying code for the infinite hexagonal grid New bounds on the minimum density of an identifying code for the infinite hexagonal grid](/preview/png/419368.png)
چکیده انگلیسی
For a graph, GG, and a vertex v∈V(G)v∈V(G), let N[v]N[v] be the set of vertices adjacent to and including vv. A set D⊆V(G)D⊆V(G) is a (vertex) identifying code if for any two distinct vertices v1,v2∈V(G)v1,v2∈V(G), the vertex sets N[v1]∩DN[v1]∩D and N[v2]∩DN[v2]∩D are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of 37≈0.428571, and this remains the best known upper bound. Until now, the best known lower bound was 1229≈0.413793 and was proved by Cranston and Yu in 2009. We present three new codes with a density of 37, and we improve the lower bound to 512≈0.416667.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2910–2924
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2910–2924
نویسندگان
Ari Cukierman, Gexin Yu,