Some Multi-Color Ramsey Numbers on Stars versus Path, Cycle or Wheel

被引:0
作者
Longqin Wang
机构
[1] Nanjing University,Department of Mathematics
[2] Jiangsu Normal University,School of Mathematics and Statistics
来源
Graphs and Combinatorics | 2020年 / 36卷
关键词
Ramsey number; Path; Star; Cycle; Wheel;
D O I
暂无
中图分类号
学科分类号
摘要
For given simple graphs H1,H2,…,Ht\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_1,H_2,\ldots ,H_t$$\end{document}, the Ramsey number R(H1,H2,…,Ht)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(H_1,H_2,\ldots ,H_t)$$\end{document}, which is often called multi-color Ramsey number, is the smallest integer n such that for an arbitrary decomposition {Gi}i=1t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{G_i\}_{i=1}^t$$\end{document} of the complete graph Kn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_n$$\end{document}, there is at least one Gi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_i$$\end{document} has a subgraph isomorphic to Hi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_i$$\end{document}. Let m,n1,n2,…,nt\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m,n_1,n_2,\ldots , n_t$$\end{document} be positive integers and Σ=∑i=1t(ni-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Sigma =\sum _{i=1}^t(n_i-1)$$\end{document}. Raeisi and Zaghian obtained the R(K1,n1,…,K1,nt,Cm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},C_m)$$\end{document} and R(K1,n1,…,K1,nt,Wm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},W_m)$$\end{document} for odd m≤Σ+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\le \Sigma +2$$\end{document}. In this paper, we establish R(K1,n1,…,K1,nt,Wm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},W_m)$$\end{document} for odd m≥Σ+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\ge \Sigma +3$$\end{document} and even m≥2Σ+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\ge 2\Sigma +2$$\end{document}. We also determine the rest values of R(K1,n1,…,K1,nt,Cm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},C_m)$$\end{document} except for even m≤Σ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\le \Sigma +1$$\end{document} and R(K1,n1,…,K1,nt,Pm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},P_m)$$\end{document} for m≥Σ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\ge \Sigma +1$$\end{document}, or m≤Σ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\le \Sigma $$\end{document} and Σ≡0,1(modm-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Sigma \equiv 0,1(\text{ mod }\, m-1)$$\end{document}, which extends a result on R(K1,n1,…,K1,nt,Pm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{1,n_1},\ldots ,K_{1,n_t},P_m)$$\end{document} obtained by K. Zhang and S. Zhang.
引用
收藏
页码:515 / 524
页数:9
相关论文
共 24 条
[1]  
Bondy JA(1971)Pancyclic graphs J. Comb Theory Ser B 11 80-84
[2]  
Boza L(2010)On the Ramsey numbers for stars versus complete graphs Eur. J. Comb. 31 1680-1688
[3]  
Cera M(1998)Weakly pancyclic graphs J. Graph Theory 27 141-176
[4]  
Garcia-Vázquez P(1975)On Ramsey graph numbers for stars and stripes Can. Math. Bull. 18 252-256
[5]  
Revuelta MP(1952)Some theorems on abstract graphs Proc. Lond. Math. Soc. 2 69-81
[6]  
Brandt S(1975)On Hanilton circuits and 1-factors of the regular complete n-partite graphs Acta Acad. Pedagog. Civitate Press Ser. 19 5-10
[7]  
Faudree R(1992)The chromatic index of complete multipartite graphs J. Graph Theory 16 159-163
[8]  
Goddard W(1984)On the Ramsey number for stars and a complete graph Ars Comb. 17 167-172
[9]  
Cockayne EJ(1976)On decomposition of r-partite graphs into edge-disjoint Hamilton circuits Discret. Math. 14 265-268
[10]  
Lorrimer PJ(2011)A note on Ramsey number of stars-complete graphs Eur. J. Comb. 32 598-599