کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650945 1342512 2006 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Longest path partitions in generalizations of tournaments
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Longest path partitions in generalizations of tournaments
چکیده انگلیسی

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D  , 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 D, there exists a partition of D   into two digraphs, D1D1 and D2D2, such that the order of a longest path in DiDi is at most λiλi, for i=1,2i=1,2.We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 16, 28 August 2006, Pages 1830–1839
نویسندگان
, , ,