کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
392890 | 665195 | 2012 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hamiltonian cycles in hypercubes with 2n-42n-4 faulty edges
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we consider Hamiltonian cycles in hypercubes with faulty edges and present a simple proof that the hypercube QnQn is not Hamiltonian if it contains a subgraph T such that: (i) exactly half of the vertices in T have parity 0 (the other half have parity 1) and (ii) all edges joining the nodes of parity 0 (or 1) with nodes outside T, are faulty. We will call such a subgraph a trap disconnected halfway . Moreover, we show that for n⩾5n⩾5, the cube QnQn with 2n-42n-4 faulty edges is not Hamiltonian only if it contains a trap T disconnected halfway with T being a subcube of dimension 1 or 2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 215, 15 December 2012, Pages 75–82
Journal: Information Sciences - Volume 215, 15 December 2012, Pages 75–82
نویسندگان
Andrzej Szepietowski,