کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647371 | 1632421 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
ترجمه فارسی عنوان
مطابقت های پیشنهادی به سیکل های همیلتون در هیپرکوب با لبه های معیوب گسترش می یابد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هیککوبه، چرخه همیلتون تطابق، خطای تحمل لبه
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Ruskey and Savage asked the following question: for n≥2n≥2, does every matching in QnQn extend to a Hamiltonian cycle in QnQn? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras’ conjecture. In this paper we consider the question in hypercubes with faulty edges. We show for n≥2n≥2 that every matching MM of at most 2n−12n−1 edges extends to a Hamiltonian cycle in QnQn. Moreover, we prove that when n≥4n≥4 and MM is nonempty this conclusion still holds even if QnQn has at most n−1−⌈|M|2⌉ faulty edges, with one exception.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 321, 28 April 2014, Pages 35–44
Journal: Discrete Mathematics - Volume 321, 28 April 2014, Pages 35–44
نویسندگان
Fan Wang, Heping Zhang,