کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
396060 | 666112 | 2007 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hamiltonian laceability of bubble-sort graphs with edge faults
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
It is known that the n-dimensional bubble-sort graph Bn is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, Bn − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of Bn. We next show that Bn − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that Bn − F has a path of length n! − 2 between any pair of vertices in the same partite set.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 177, Issue 13, 1 July 2007, Pages 2679–2691
Journal: Information Sciences - Volume 177, Issue 13, 1 July 2007, Pages 2679–2691
نویسندگان
Toru Araki, Yosuke Kikuchi,