|
|
پژوهش های ریاضی، جلد ۷، شماره ۳، صفحات ۴۸۵-۴۹۴
|
|
|
| عنوان فارسی |
عدد رمزی یالی چند رنگی مسیرها |
|
| چکیده فارسی مقاله |
گراف $ F $ که با نماد
$ hat{r}(F,r) $ نشان داده میشود، برابر است با کوچکترین عدد صحیح $ m $ بهطوری که یک گراف $ G $ با $ m $ یال وجود داشته باشد که در هر رنگآمیزی از یالهای گراف $ G $ با $ r $ رنگ، یک کپی تک رنگ از گراف $ F $ وجود داشته باشد. کریولویچ و بهطور جداگانه دودک و پرالات برای مسیرهای $ P_n $ نشان دادهاند که برای $ n $ به اندازه کافی بزرگ، $ hat{r}(P_n, r) leq 600 r^2(ln r) n$. در این مقاله ما با اثباتی کاملا متفاوت این کران را بهبود داده و ثابت میکنیم $ hat{r}(P_n, r) leq 18(1+o_r(1)) r^2(ln r) n$. لازم به تذکر است که کران بالای بهدست آمده تقریباً بهینه است، زیرا میدانیم که $ hat{r}(P_n, r) = Omega(r^2n) $. |
|
| کلیدواژههای فارسی مقاله |
عدد رمزی،عدد رمزی یالی،مسیر، |
|
| عنوان انگلیسی |
Multicolor Size-Ramsey Number of Paths |
|
| چکیده انگلیسی مقاله |
The size-Ramsey number of a graph denoted by is the smallest integer such that there is a graph with edges with this property that for any coloring of the edges of with colors, contains a monochromatic copy of. The investigation of the size-Ramsey numbers of graphs was initiated by Erdős‚ Faudree‚ Rousseau and Schelp in 1978. Since then, Size-Ramsey numbers have been studied with particular focus on the case of trees and bounded degree graphs.
Addressing a question posed by Erdős‚ Beck [2] proved that the size-Ramsey number of the path is linear in by means of a probabilistic construction. In fact, Beck’s proof implies that and this upper bound was improved several times. Currently‚ the best known upper bound is due to Dudek and Prałat [4] which proved that . On the other hand‚ the first nontrivial lower bound for was provided by Beck and his result was subsequently improved by Dudek and Prałat [3] who showed that. The strongest known lower bound was proved recently by Bal and DeBiasio [1].
./files/site1/files/%D8%AC%D9%88%D8%A7%D8%AF%DB%8C_%D9%85%DB%8C%D8%B1%D8%B9%D9%84%D8%A7%DB%8C%DB%8C.pdf |
|
| کلیدواژههای انگلیسی مقاله |
عدد رمزی,عدد رمزی یالی,مسیر |
|
| نویسندگان مقاله |
رامین جوادی |
دانشگاه صنعتی اصفهان
میثم میرعلایی |
دانشگاه صنعتی اصفهان
|
|
| نشانی اینترنتی |
https://mmr.khu.ac.ir/article_8726_d6f84c02e2a54908d96f410083beb6e0.pdf |
| فایل مقاله |
فایلی برای مقاله ذخیره نشده است |
| کد مقاله (doi) |
|
| زبان مقاله منتشر شده |
fa |
| موضوعات مقاله منتشر شده |
|
| نوع مقاله منتشر شده |
|
|
|
|
برگشت به:
صفحه اول پایگاه |
نسخه مرتبط |
نشریه مرتبط |
فهرست نشریات
|
