| Title:
|
Ramsey numbers for trees II (English) |
| Author:
|
Sun, Zhi-Hong |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
2 |
| Year:
|
2021 |
| Pages:
|
351-372 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $r(G_1, G_2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. For $n_1\ge n_2\ge 1$ let $S(n_1,n_2)$ be the double star given by $V(S(n_1,n_2))=\{v_0,v_1,\ldots ,v_{n_1},w_0$, $w_1,\ldots ,w_{n_2}\}$ and $E(S(n_1,n_2))=\{v_0v_1,\ldots ,v_0v_{n_1},v_0w_0, w_0w_1,\ldots ,w_0w_{n_2}\}$. We determine $r(K_{1,m-1},$ $S(n_1,n_2))$ under certain conditions. For $n\ge 6$ let $T_n^3=S(n-5,3)$, $T_n''=(V,E_2)$ and $T_n''' =(V,E_3)$, where $V=\{v_0,v_1,\ldots ,v_{n-1}\}$, $E_2=\{v_0v_1,\ldots ,v_0v_{n-4},v_1v_{n-3}$, $v_1v_{n-2}, v_2v_{n-1}\}$ and $E_3=\{v_0v_1,\ldots , v_0v_{n-4},v_1v_{n-3},$ $v_2v_{n-2},v_3v_{n-1}\}$. We also obtain explicit formulas for $r(K_{1,m-1},T_n)$, $r(T_m',T_n)$ $(n\ge m+3)$, $r(T_n,T_n)$, $r(T_n',T_n)$ and $r(P_n,T_n)$, where $T_n\in \{T_n'',T_n''',T_n^3\}$, $P_n$ is the path on $n$ vertices and $T_n'$ is the unique tree with $n$ vertices and maximal degree $n-2$. (English) |
| Keyword:
|
Ramsey number |
| Keyword:
|
tree |
| Keyword:
|
Turán's problem |
| MSC:
|
05C05 |
| MSC:
|
05C35 |
| MSC:
|
05C55 |
| idZBL:
|
07361073 |
| idMR:
|
MR4263174 |
| DOI:
|
10.21136/CMJ.2021.0328-19 |
| . |
| Date available:
|
2021-05-20T13:40:40Z |
| Last updated:
|
2023-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148909 |
| . |
| Reference:
|
[1] Burr, S. A., Erdős, P.: Extremal Ramsey theory for graphs.Util. Math. 9 (1976), 247-258. Zbl 0333.05119, MR 0429622 |
| Reference:
|
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs.Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1986). Zbl 0666.05001, MR 0834583, 10.1201/b19731 |
| Reference:
|
[3] Faudree, R. J., Schelp, R. H.: Path Ramsey numbers in multicolorings.J. Comb. Theory, Ser. B 19 (1975), 150-160. Zbl 0286.05111, MR 0412023, 10.1016/0095-8956(75)90080-5 |
| Reference:
|
[4] Grossman, J. W., Harary, F., Klawe, M.: Generalized Ramsey theory for graphs, X: Double stars.Discrete Math. 28 (1979), 247-254. Zbl 0434.05052, MR 0548624, 10.1016/0012-365X(79)90132-8 |
| Reference:
|
[5] Guo, Y., Volkmann, L.: Tree-Ramsey numbers.Australas. J. Comb. 11 (1995), 169-175. Zbl 0828.05043, MR 1327331 |
| Reference:
|
[6] Harary, F.: Recent results on generalized Ramsey theory for graphs.Graph Theory and Applications Lecture Notes in Mathematics 303. Springer, Berlin (1972), 125-138. Zbl 0247.05118, MR 0342431, 10.1007/BFb0067364 |
| Reference:
|
[7] Hua, L. K.: Introduction to Number Theory.Springer, Berlin (1982). Zbl 0483.10001, MR 0665428, 10.1007/978-3-642-68130-1 |
| Reference:
|
[8] Radziszowski, S. P.: Small Ramsey numbers.Electron. J. Comb. 2017 (2017), Article ID DS1, 104 pages. MR 1670625, 10.37236/21 |
| Reference:
|
[9] Sun, Z.-H.: Ramsey numbers for trees.Bull. Aust. Math. Soc. 86 (2012), 164-176. Zbl 1247.05150, MR 2960237, 10.1017/S0004972711003388 |
| Reference:
|
[10] Sun, Z.-H., Tu, Y.-Y.: Turán's problem for trees $T_n$ with maximal degree $n-4$.Available at https://arxiv.org/abs/1410.7282 (2014), 28 pages. |
| Reference:
|
[11] Sun, Z.-H., Wang, L.-L.: Turán's problem for trees.J. Comb. Number Theory 3 (2011), 51-69. Zbl 1247.05117, MR 2908182 |
| Reference:
|
[12] Sun, Z.-H., Wang, L.-L., Wu, Y.-L.: Turán's problem and Ramsey numbers for trees.Colloq. Math. 139 (2015), 273-298. Zbl 1312.05089, MR 3337221, 10.4064/cm139-2-8 |
| . |
