کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421133 684142 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Quasi-Hamiltonian cycles in kk-strong multipartite tournaments
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Quasi-Hamiltonian cycles in kk-strong multipartite tournaments
چکیده انگلیسی

A cc-partite tournament is an orientation of a complete cc-partite graph. Recently, M. Lu, et al., introduced the concept of quasi-Hamiltonian cycles, that is to say, cycles containing vertices from each partite set, in multipartite tournaments. W.D. Goddard and O.R. Oellermann established that every strong multipartite tournament contains a quasi-Hamiltonian cycle.In this paper, we show that every kk-strong (or kk-arc-strong) multipartite tournament contains at least kk quasi-Hamiltonian cycles. To that end, we prove the following stronger result: Every strong multipartite tournament contains a vertex whose all out-arcs are contained in a quasi-Hamiltonian cycle. Our results include and extend corresponding ones concerning tournaments due to C. Thomassen, as well as M. Goldberg and J.W. Moon.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 253–257
نویسندگان
,