کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776981 | 1413647 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ramsey numbers of trees and unicyclic graphs versus fans
ترجمه فارسی عنوان
تعداد رمزی درختان و نمودارهای غیر کلاسیک در مقابل طرفداران
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The generalized Ramsey number R(H,K) is the smallest positive integer n such that for any graph G with n vertices either G contains H as a subgraph or its complement G¯ contains K as a subgraph. Let Tn be a tree with n vertices and Fm be a fan with 2m+1 vertices consisting of m triangles sharing a common vertex. We prove a conjecture of Zhang, Broersma and Chen for mâ¥9 that R(Tn,Fm)=2nâ1 for all nâ¥m2âm+1. Zhang, Broersma and Chen showed that R(Sn,Fm)â¥2n for nâ¤m2âm where Sn is a star on n vertices, implying that the lower bound we show is in some sense tight. We also extend this result to unicyclic graphs UCn, which are connected graphs with n vertices and a single cycle. We prove that R(UCn,Fm)=2nâ1 for all nâ¥m2âm+1 where mâ¥18. In proving this conjecture and extension, we present several methods for embedding trees in graphs, which may be of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 969-983
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 969-983
نویسندگان
Matthew Brennan,