کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871520 | 1440187 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the existence of vertex-disjoint subgraphs with high degree sum
ترجمه فارسی عنوان
در وجود زیرگرافهای ارجاعی بدون ارقام با مجموعهای بالایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
For a graph G, we denote by Ï2(G) the minimum degree sum of two non-adjacent vertices if G is non-complete; otherwise, Ï2(G)=+â. In this paper, we prove the following two results: (i) If s1,s2â¥2 are integers and G is a non-complete graph with Ï2(G)â¥2(s1+s2+1)â1, then G contains two vertex-disjoint subgraphs H1 and H2 such that each Hi is a graph of order at least si+1 with Ï2(Hi)â¥2siâ1. (ii) If s1,s2â¥2 are integers and G is a triangle-free graph of order at least 3 with Ï2(G)â¥2(s1+s2)â1, then G contains two vertex-disjoint subgraphs H1 and H2 such that each Hi is a graph of order at least 2si with Ï2(Hi)â¥2siâ1. By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 84-95
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 84-95
نویسندگان
Shuya Chiba, Nicolas Lichiardopol,