کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647021 | 1342322 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On a local similarity of graphs
ترجمه فارسی عنوان
در یک شباهت محلی از نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شباهت گراف ها، زیرگرافهای منجر شده است
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We say that two graphs GG and HH, having the same number of vertices nn, are kk-similar if they contain a common induced subgraph of order kk. We will consider the following question: how large does nn need to be to ensure at least one kk-similar pair in any family of ll graphs on nn vertices? We will present various lower and upper bounds on nn. In particular, we will prove that for l=3l=3, nn equals the Ramsey number R(k,k)R(k,k). Last but not least we will determine the exact values of nn for k=3k=3, k=4k=4 and all ll.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 6, 6 June 2015, Pages 983–989
Journal: Discrete Mathematics - Volume 338, Issue 6, 6 June 2015, Pages 983–989
نویسندگان
Tomasz Dzido, Krzysztof Krzywdziński,