The Ramsey Numbers of Trees Versus Generalized Wheels

被引:0
作者
Longqin Wang
Yaojun Chen
机构
[1] Nanjing University,Department of Mathematics
[2] Jiangsu Normal University,School of Mathematics and Statistics
来源
Graphs and Combinatorics | 2019年 / 35卷
关键词
Ramsey number; Path; Star; Tree; Generalized wheel;
D O I
暂无
中图分类号
学科分类号
摘要
For two given graphs G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} and G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_2$$\end{document}, the Ramsey number R(G1,G2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(G_1,G_2)$$\end{document} is the smallest integer n such that for any graph G of order n, either G contains G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} or its complement G¯\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{G}}$$\end{document} contains G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_2$$\end{document}. Let Pn,Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_n, S_n$$\end{document} and Tn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_n$$\end{document} denote a path, a star and a tree of order n, respectively. A generalized wheel, denoted by Ws,m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W_{s,m}$$\end{document}, is the join of a complete graph Ks\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_s$$\end{document} and a cycle Cm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_m$$\end{document}. In this paper, we show that R(Tn,Ws,4)=(n-1)(s+1)+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(T_n,W_{s,4})=(n-1)(s+1)+1$$\end{document} for n≥3,s≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3,s\ge 2$$\end{document} and R(Tn,Ws,5)=(n-1)(s+2)+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(T_n,W_{s,5})=(n-1)(s+2)+1$$\end{document} for n≥3,s≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3,s\ge 1$$\end{document}. These generalize some known results on Ramsey numbers for a tree versus a wheel.
引用
收藏
页码:189 / 193
页数:4
相关论文
共 21 条
  • [1] Baskoro ET(2002)On Ramsey numbers for trees versus wheels of five or six vertices Graphs Comb. 18 717-721
  • [2] Nababan SM(1971)Pancyclic graphs J. Comb. Theory Ser. B 11 80-84
  • [3] Miller M(1981)Ramsey numbers involving graphs with long suspended paths J. Lond. Math. Soc. 24 405-413
  • [4] Bondy JA(2005)The Ramsey numbers of paths versus wheels Discrete Math. 290 85-87
  • [5] Burr SA(2004)The Ramsey numbers of stars versus wheels Eur. J. Comb. 25 1067-1075
  • [6] Chen Y(2005)Star-wheel Ramsey numbers J. Comb. Math. Comb. Comput. 55 123-128
  • [7] Zhang Y(2010)Ramsey goodness and generalized stars Eur. J. Comb. 31 1228-1234
  • [8] Zhang K(2017)Small Ramsey numbers Electron. J. Comb. DS1 15-232
  • [9] Chen Y(1994)Paths, cycles and wheels without antitriangles Australas. J. Comb. 9 221-20
  • [10] Zhang Y(2008)On Ramsey numbers of short paths versus large wheels ARS Comb. 89 11-undefined