کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9514605 | 1632609 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the Structure of Identifiable Graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Consider a connected undirected graph G=(V,E), a subset of vertices CâV, and an integer râ¥1; for any vertex vâV, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices linked to v by a path of at most r edges. If for all vertices vâV, the sets Br(v)â©C are all nonempty and different, then we call C an r-identifying code. A graph is said to be r-identifiable if it admits at least one r-identifying code. We prove the following structural properties of r-identifiable graphs. For any râ¥1, any r-identifiable graph must have at least 2r+1 vertices. For r=1 and for any r-identifiable graph G with at least 2r+2 vertices, or for any râ¥1 and for any r-identifiable tree G with at least 2r+2 vertices, there always exists at least one vertex such that its removing from G leaves an r-identifiable graph. This property is not true for râ¥3 in general. The case r=2 remains open for general graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 491-495
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 491-495
نویسندگان
Irène Charon, Olivier Hudry, Antoine Lobstein,