کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903607 1632747 2018 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Highly connected subgraphs of graphs with given independence number
ترجمه فارسی عنوان
زیرگراف های بسیار متصل به گراف ها با تعداد استقلال داده شده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G be a graph on n vertices with independence number α. We prove that if n is sufficiently large (n≥α2k+1 will do), then G always contains a k-connected subgraph on at least n∕α vertices. The value of n∕α 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 respectively, and that these lower bounds on n are sharp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 70, May 2018, Pages 212-231
نویسندگان
, , ,