کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424365 1632785 2013 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
چکیده انگلیسی

The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta-Häggkvist conjecture says that every digraph with n vertices and minimum out-degree r contains a cycle of length at most ⌈n/r⌉. We give a proof of the former conjecture for digraphs with out-degree r and connectivity r−1, and of the second one for digraphs with connectivity r−1 and r≥n/3. The main tool is the isoperimetric method of Hamidoune.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 34, Issue 8, November 2013, Pages 1406-1410
نویسندگان
,