کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903489 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum density of identifying codes of king grids
ترجمه فارسی عنوان
حداقل تراکم شناسایی کدهای شبکه های پادشاه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کد شناسایی، شبکه کینگ، روش تخلیه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A set CâV(G) is an identifying code in a graph G if for all vâV(G), C[v]â â
, and for all distinct u,vâV(G), C[u]â C[v], where C[v]=N[v]â©C and N[v] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by dâ(G). In this paper, we study the density of king grids which are strong product of two paths. We show that for every king grid G,dâ(G)â¥2/9. In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given kâ¥3, we denote by Kk the (infinite) king strip with k rows. We prove that dâ(K3)=1/3, dâ(K4)=5/16, dâ(K5)=4/15 and dâ(K6)=5/18. We also prove that 29+881kâ¤dâ(Kk)â¤29+49k for every kâ¥7.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 51-56
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 51-56
نویسندگان
Rennan Dantas, Rudini M. Sampaio, Frédéric Havet,