کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903057 1632401 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The parity Hamiltonian cycle problem
ترجمه فارسی عنوان
مسئله چرخه هامیلتونی تقارن
کلمات کلیدی
مشکل چرخه همیلتون تی پیوست عامل گراف،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
, , , , ,