کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651082 | 1632445 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Independence number and vertex-disjoint cycles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Independence number and vertex-disjoint cycles Independence number and vertex-disjoint cycles](/preview/png/4651082.png)
چکیده انگلیسی
In this paper we consider graphs which have no k vertex-disjoint cycles. For given integers k,αk,α let f(k,α)f(k,α) be the maximum order of a graph G with independence number α(G)⩽αα(G)⩽α, which has no k vertex-disjoint cycles. We prove that f(k,α)=3k+2α-3f(k,α)=3k+2α-3 if 1⩽α⩽51⩽α⩽5 or 1⩽k⩽21⩽k⩽2, and f(k,α)⩾3k+2α-3f(k,α)⩾3k+2α-3 in general. We also prove the following results: (1) there exists a constant cαcα (depending only on αα) such that f(k,α)⩽3k+cαf(k,α)⩽3k+cα, (2) there exists a constant tktk (depending only on k ) such that f(k,α)⩽2α+tkf(k,α)⩽2α+tk, and (3) there exists no absolute constant c such that f(k,α)⩽c(k+α)f(k,α)⩽c(k+α).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1493–1498
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1493–1498
نویسندگان
Yoshimi Egawa, Hikoe Enomoto, Stanislav Jendrol, Katsuhiro Ota, Ingo Schiermeyer,