Ramsey Numbers for Trees II
Ramsey Numbers for Trees II
复制标题
DOI：
10.21136/cmj.2021.0328-19
复制
发表时间：
2014-10
影响因子：
0.5
通讯作者：
Zhi-Hong Sun
中科院分区：
文献类型：
--
作者：
Zhi-Hong Sun
Let r(G1, G2) be the Ramsey number of the two graphs G1 and G2. For n1 ≽ n2 ≽ 1 let S(n1, n2) be the double star given by V(S(n1,n2))={v0,v1,…,vn1,w0,w1,…,wn2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\left( {S\left( {{n_1},{n_2}} \right)} \right) = \left\{ {{v_0},{v_1}, \ldots ,{v_{{n_1}}},{w_0},{w_1}, \ldots ,{w_{{n_2}}}} \right\}$$\end{document} and E(S(n1,n2))={v0v1,…,v0vn1,v0w0,w0w1,…,w0wn2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E\left( {S\left( {{n_1},{n_2}} \right)} \right) = \left\{ {{v_0}{v_1}, \ldots ,{v_0}{v_{{n_1}}},{v_0}{w_0},{w_0}{w_1}, \ldots ,{w_0}{w_{{n_2}}}} \right\}$$\end{document}. We determine r(K1,m−1, S(n1, n2)) under certain conditions. For n ≽ 6 let Tn3 − S(n − 5, 3), Tn″ − (V, E2) and Tn‴ = (V, E3), where V = {v0, v1, …, vn−1}, E2 = {v0v1, …, v0vn−4, v1vn−3, v1vn−2, v2vn−1} and E3 = {v0v1, …, v0vn−4, v1vn−3, v2vn−2, v3vn−1}. We also obtain explicit formulas for r(K1,m−1, Tn), r(Tm′,Tn) (n ≽ m + 3), r(Tn, Tn), r(Tn′, Tn) and r(Pn, Tn), where Tn ∈ {Tn″, Tn‴, Tn3}, Pn is the path on n vertices and Tn′ is the unique tree with n vertices and maximal degree n − 2.
Let r(G1, G2) be the Ramsey number of the two graphs G1 and G2. For n1 ≽ n2 ≽ 1 let S(n1, n2) be the double star given by V(S(n1,n2))={v0,v1,…,vn1,w0,w1,…,wn2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\left( {S\left( {{n_1},{n_2}} \right)} \right) = \left\{ {{v_0},{v_1}, \ldots ,{v_{{n_1}}},{w_0},{w_1}, \ldots ,{w_{{n_2}}}} \right\}$$\end{document} and E(S(n1,n2))={v0v1,…,v0vn1,v0w0,w0w1,…,w0wn2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E\left( {S\left( {{n_1},{n_2}} \right)} \right) = \left\{ {{v_0}{v_1}, \ldots ,{v_0}{v_{{n_1}}},{v_0}{w_0},{w_0}{w_1}, \ldots ,{w_0}{w_{{n_2}}}} \right\}$$\end{document}. We determine r(K1,m−1, S(n1, n2)) under certain conditions. For n ≽ 6 let Tn3 − S(n − 5, 3), Tn″ − (V, E2) and Tn‴ = (V, E3), where V = {v0, v1, …, vn−1}, E2 = {v0v1, …, v0vn−4, v1vn−3, v1vn−2, v2vn−1} and E3 = {v0v1, …, v0vn−4, v1vn−3, v2vn−2, v3vn−1}. We also obtain explicit formulas for r(K1,m−1, Tn), r(Tm′,Tn) (n ≽ m + 3), r(Tn, Tn), r(Tn′, Tn) and r(Pn, Tn), where Tn ∈ {Tn″, Tn‴, Tn3}, Pn is the path on n vertices and Tn′ is the unique tree with n vertices and maximal degree n − 2.