کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777649 1632971 2017 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the Corrádi-Hajnal theorem and a question of Dirac
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the Corrádi-Hajnal theorem and a question of Dirac
چکیده انگلیسی
Enomoto and Wang refined the Corrádi-Hajnal Theorem, proving the following Ore-type version: For all k≥1 and n≥3k, every graph G on n vertices contains k disjoint cycles, provided that d(x)+d(y)≥4k−1 for all distinct nonadjacent vertices x,y. We refine this further for k≥3 and n≥3k+1: If G is a graph on n vertices such that d(x)+d(y)≥4k−3 for all distinct nonadjacent vertices x,y, then G has k vertex-disjoint cycles if and only if the independence number α(G)≤n−2k and G is not one of two small exceptions in the case k=3. We also show how the case k=2 follows from Lovász' characterization of multigraphs with no two disjoint cycles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 121-148
نویسندگان
, , ,