کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649506 1342458 2010 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two proofs of the Bermond–Thomassen conjecture for tournaments with bounded minimum in-degree
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Two proofs of the Bermond–Thomassen conjecture for tournaments with bounded minimum in-degree
چکیده انگلیسی

The Bermond–Thomassen conjecture states that, for any positive integer rr, a digraph of minimum out-degree at least 2r−12r−1 contains at least rr vertex-disjoint directed cycles. Thomassen proved that it is true when r=2r=2, and very recently the conjecture was proved for the case where r=3r=3. It is still open for larger values of rr, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−12r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 3, 6 February 2010, Pages 557–560
نویسندگان
, , ,