کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647617 1342362 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Path Partition Conjecture is true for some generalizations of tournaments
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Path Partition Conjecture is true for some generalizations of tournaments
چکیده انگلیسی

The Path Partition Conjecture for digraphs states that for every digraph DD, and every choice of positive integers λ1,λ2λ1,λ2 such that λ1+λ2λ1+λ2 equals the order of a longest directed path in DD, there exists a partition of DD in two subdigraphs D1,D2D1,D2 such that the order of the longest path in DiDi is at most λiλi for i=1,2i=1,2.We present sufficient conditions for a digraph to satisfy the Path Partition Conjecture. Using these results, we prove that strong path mergeable, arc-locally semicomplete, strong 3-quasi-transitive, strong arc-locally in-semicomplete and strong arc-locally out-semicomplete digraphs satisfy the Path Partition Conjecture. Some previous results are generalized.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 3, 6 February 2013, Pages 293–300
نویسندگان
, ,