Previous |  Up |  Next

Article

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
.

Files

Files Size Format View
CzechMathJ_71-2021-2_4.pdf 279.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo