کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647371 1632421 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
ترجمه فارسی عنوان
مطابقت های پیشنهادی به سیکل های همیلتون در هیپرکوب با لبه های معیوب گسترش می یابد
کلمات کلیدی
هیککوبه، چرخه همیلتون تطابق، خطای تحمل لبه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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
نویسندگان
, ,