کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419226 | 683753 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on the middle levels problem
ترجمه فارسی عنوان
نکته ای درباره مسئله سطوح متوسط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسیر همیلتونی؛ چرخه هامیلتونی؛ سطوح میانه نمودار؛ گراف نسر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The middle levels problem consists in determining a hamiltonian cycle in the bipartite Kneser graph B(2k+1,k)B(2k+1,k), also known as the middle levels graph and denoted by BkBk. Previously, it was proved that a particular hamiltonian path in a reduced graph of BkBk implies a hamiltonian cycle in BkBk and a hamiltonian path in the Kneser graph K(2k+1,k)K(2k+1,k). We show that the existence of such a particular hamiltonian path in a reduced graph of K(2k+3,k)K(2k+3,k) implies a hamiltonian path in K(2k+3,k)K(2k+3,k) for k≡1k≡1 or 2(mod3). Moreover, we utilize properties from the middle levels graphs to improve a known algorithm speeding up the search for such a particular hamiltonian path in the reduced graph of BkBk.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 290–296
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 290–296
نویسندگان
Andréia C.S. Gusmão, Letícia R. Bueno, Rodrigo A. Hausen, Celina M.H. Figueiredo, Luerbio Faria,