کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903057 | 1632401 | 2018 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The parity Hamiltonian cycle problem
ترجمه فارسی عنوان
مسئله چرخه هامیلتونی تقارن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل چرخه همیلتون تی پیوست عامل گراف،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a closed walk which visits every vertex an odd number of times, where we remark that the walk may use an edge more than once. First, we give a complete characterization of the graphs which have PHCs, and give a linear time algorithm to find a PHC, in which every edge appears at most four times, in fact. In contrast, we show that finding a PHC is NP-hard if a closed walk is allowed to use each edge at most z times for each z=1,2,3 (PHCz for short), even when a given graph is two-edge-connected. We then further investigate the PHC3 problem, and show that the problem is in P when an input graph is four-edge-connected. Finally, we are concerned with three (or two)-edge-connected graphs, and show that the PHC3 problem is in P for any Câ¥5-free or P6-free graphs. Note that the Hamiltonian cycle problem is known to be NP-hard for those graph classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 606-626
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 606-626
نویسندگان
Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita,