تقرير
A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid
| العنوان: | A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid |
|---|---|
| المؤلفون: | Cranston, Daniel W., Yu, Gexin |
| المصدر: | Electronic J. of Combinatorics, R113, Volume 16(1), 2009 |
| سنة النشر: | 2010 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Data Structures and Algorithms, 05C35, 05C69, 05C90 |
| الوصف: | Given a graph $G$, an identifying code $C \subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$, the sets $N[v_1]\cap C$ and $N[v_2]\cap C$ 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 et.al. 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\approx0.410256$. Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$. Comment: 16 pages, 10 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1006.3779 |
| رقم الأكسشن: | edsarx.1006.3779 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!