کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423662 | 1632577 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract)
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G be a graph on n vertices with independence number α. What is the largest k-connected subgraph that G must contain? We prove that if n is sufficiently large (nâ¥Î±2k+1 will do), then G contains a k-connected subgraph on at least n/α vertices. This is sharp, since G might be the disjoint union of α equally-sized cliques. For kâ¥3 and α=2,3, we shall prove that the same result holds for nâ¥4(kâ1) and nâ¥27(kâ1)4 sharp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 103-108
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 103-108
نویسندگان
Shinya Fujita, Henry Liu, Amites Sarkar,