On the Star-Critical Ramsey Number of a Forest Versus Complete Graphs

被引:0
作者
Azam Kamranian
Ghaffar Raeisi
机构
[1] Shahrekord University,Department of Mathematical Sciences
来源
Iranian Journal of Science and Technology, Transactions A: Science | 2022年 / 46卷
关键词
Ramsey number; Star-critical; Size Ramsey; Forest; Complete graphs; 05D10; 05C55; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
Let G and G1,G2,…,Gt\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1, G_2, \ldots , G_t$$\end{document} be given graphs. By G→(G1,G2,…,Gt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G\rightarrow (G_1, G_2, \ldots , G_t)$$\end{document}, we mean if the edges of G are arbitrarily colored by t colors, then for some i, 1≤i≤t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\le i\le t$$\end{document}, the spanning subgraph of G whose edges are colored with the i-th color, contains a copy of 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}. The Ramsey number R(G1,G2,…,Gt)\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, \ldots , G_t)$$\end{document} is the smallest positive integer n such that Kn→(G1,G2,…,Gt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_n\rightarrow (G_1, G_2, \ldots , G_t)$$\end{document}, and the size Ramsey number R^(G1,G2,…,Gt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\hat{R}}(G_1, G_2, \ldots , G_t)$$\end{document} is defined as min{|E(G)|:G→(G1,G2,…,Gt)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{|E(G)|:~G\rightarrow (G_1, G_2, \ldots , G_t)\}$$\end{document}. Also, for given graphs G1,G2,…,Gt\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1, G_2, \ldots , G_t$$\end{document} with r=R(G1,G2,…,Gt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r=R(G_1, G_2, \ldots , G_t)$$\end{document}, the star-critical Ramsey number R∗(G1,G2,…,Gt)\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, \ldots , G_t)$$\end{document} is defined as min{δ(G):G⊆Kr,G→(G1,G2,…,Gt)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{\delta (G):~G\subseteq K_r, ~G\rightarrow (G_1, G_2, \ldots , G_t)\}$$\end{document}. In this paper, the Ramsey number and also the star-critical Ramsey number of a forest versus any number of complete graphs will be computed exactly in terms of the Ramsey number of the complete graphs. As a result, the computed star-critical Ramsey number is used to give a tight bound for the size Ramsey number of a forest versus a complete graph.
引用
收藏
页码:499 / 505
页数:6
相关论文
共 40 条
[1]  
Beck J(1983)On size Ramsey number of paths, trees and circuits I J Graph Theory 7 115-129
[2]  
Burr SA(1976)On graphs of Ramsey type Ars Comb 1 167-190
[3]  
Erdős P(2012)The size-Ramsey number of trees Random Struct Algorithms 40 49-73
[4]  
Lovász L(2005)A note on the size-Ramsey number of long subdivisions of graphs RAIRO Theor Inform Appl 39 191-206
[5]  
Dellamonica D(1978)The size Ramsey number Period Math Hung 9 145-161
[6]  
Donadelli J(1984)Size Ramsey numbers involving matchings Finite Infinite Sets 37 247-264
[7]  
Haxell PE(1970)Graphs with monochromatic complete subgraphs in every edge coloring SIAM J Appl Math 18 19-24
[8]  
Kohayakawa Y(2011)Degree Ramsey numbers of closed blowups of trees Star-critical Ramsey numbers. Discret Appl Math 159 328-334
[9]  
Erdős P(2014)Degree Ramsey numbers for cycles and blowups of trees Electron J Comb 21 2-5
[10]  
Faudree RJ(2013)Decomposition of bounded degree graphs into Eur J Comb 34 414-423