Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Ramsey number; tree; Turán's problem
Ramsey number; tree; Turán's problem
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$.
References:
[1] Burr, S. A., Erdős, P.: Extremal Ramsey theory for graphs. Util. Math. 9 (1976), 247-258. MR 0429622 | Zbl 0333.05119
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs. Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1986). DOI 10.1201/b19731 | MR 0834583 | Zbl 0666.05001
[3] Faudree, R. J., Schelp, R. H.: Path Ramsey numbers in multicolorings. J. Comb. Theory, Ser. B 19 (1975), 150-160. DOI 10.1016/0095-8956(75)90080-5 | MR 0412023 | Zbl 0286.05111
[4] Grossman, J. W., Harary, F., Klawe, M.: Generalized Ramsey theory for graphs, X: Double stars. Discrete Math. 28 (1979), 247-254. DOI 10.1016/0012-365X(79)90132-8 | MR 0548624 | Zbl 0434.05052
[5] Guo, Y., Volkmann, L.: Tree-Ramsey numbers. Australas. J. Comb. 11 (1995), 169-175. MR 1327331 | Zbl 0828.05043
[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. DOI 10.1007/BFb0067364 | MR 0342431 | Zbl 0247.05118
[7] Hua, L. K.: Introduction to Number Theory. Springer, Berlin (1982). DOI 10.1007/978-3-642-68130-1 | MR 0665428 | Zbl 0483.10001
[8] Radziszowski, S. P.: Small Ramsey numbers. Electron. J. Comb. 2017 (2017), Article ID DS1, 104 pages. DOI 10.37236/21 | MR 1670625
[9] Sun, Z.-H.: Ramsey numbers for trees. Bull. Aust. Math. Soc. 86 (2012), 164-176. DOI 10.1017/S0004972711003388 | MR 2960237 | Zbl 1247.05150
[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.
[11] Sun, Z.-H., Wang, L.-L.: Turán's problem for trees. J. Comb. Number Theory 3 (2011), 51-69. MR 2908182 | Zbl 1247.05117
[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. DOI 10.4064/cm139-2-8 | MR 3337221 | Zbl 1312.05089
Search
Partner of
