کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903583 1632746 2018 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On splitting digraphs
ترجمه فارسی عنوان
در تقسیم دیفرانسیل
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In 1995, Stiebitz asked the following question: For any positive integers s,t, is there a finite integer f(s,t) such that every digraph D with minimum out-degree at least f(s,t) admits a bipartition (A,B) such that A induces a subdigraph with minimum out-degree at least s and B induces a subdigraph with minimum out-degree at least t? We give an affirmative answer for tournaments, multipartite tournaments, and digraphs with bounded maximum in-degrees. In particular, we show that for every ϵ with 0<ϵ<1∕2, there exists an integer δ0 such that every tournament with minimum out-degree at least δ0 admits a bisection (A,B), so that each vertex has at least (1∕2−ϵ) of its out-neighbors in A, and in B as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 71, June 2018, Pages 174-179
نویسندگان
, , , ,