对于轮和完全图的 Ramsey 数的渐近上界

数学物理学报

对于轮和完全图的 Ramsey 数的渐近上界

宋洪雪;白路峰; 刘书彦

南京邮电大学数理学院南京 210003

收稿日期:2004-03-21 修回日期:2005-12-28 出版日期:2006-10-25 发布日期:2006-10-25
通讯作者: 宋洪雪
基金资助:
国家自然科学基金(19871023)和江苏省自然科学基金资助

Asymptotic Upper Bounds for Wheel: Complete Graph Ramsey Numbers

Song Hongxue ; Bai Lufeng; Liu Shuyan

College of Sciences, Nanjing University of Posts and Telecommunications, Nanjing 210003

Received:2004-03-21 Revised:2005-12-28 Online:2006-10-25 Published:2006-10-25
Contact: Song Hongxue

摘要/Abstract

摘要：

该文给出:对于偶数m≥4当n→ ∞时
r(W_m,K_n)≤l(1+o(1))C₁(m) (n/logn ) ^(2m-2)/(m-2)

对于奇数m≥5当n→∞时
r(W_m,K_n)≤(1+o(1))C₂(m) (n^2m/_m+1/_{^{log n)}}^(m+1)/(m-1) .

特别地,C₂(5)=12. 以及 c(ⁿ/_logn)^5/2≤r(K₄,K_n)≤ (1+o(1)) ^n3_/(logn)².
此外,该文还讨论了轮和完全图的 Ramsey 数的一些推广.

关键词: Ramsey 数, 轮, 独立数, 完全图

Abstract: It is shown that r(W_m,K_n)≤l(1+o(1))C₁(m) (n/logn ) ^(2m-2)/(m-2)
for fixed even
r(W_m,K_n)≤(1+o(1))C₂(m) (n^2m/_m+1/_{^{log n)}}^(m+1)/(m-1) for fixed odd m≥5 and n→∞. In particular, C₂(5)=12 . Also, c(ⁿ/_logn)^5/2≤r(K₄,K_n)≤ (1+o(1)) ^n3_/(logn)². Moreover, in this paper, the authors discuss some generalizations for wheel: complete graph Ramsey numbers.

Key words: Ramsey numbers, Wheels

中图分类号:

05C55

宋洪雪;白路峰; 刘书彦. 对于轮和完全图的 Ramsey 数的渐近上界[J]. 数学物理学报, 2006, 26(5): 741-746.

Song Hongxue ; Bai Lufeng; Liu Shuyan.

Asymptotic Upper Bounds for Wheel: Complete Graph Ramsey Numbers

[J]. Acta mathematica scientia,Series A, 2006, 26(5): 741-746.

[1]	尹建华. 有一个实现包含K_r₊₁的可图序列[J]. 数学物理学报, 2009, 29(5): 1376-1389.
[2]	陈东; 王维凡. 一些图的生成树数[J]. 数学物理学报, 2008, 28(5): 906-913.
[3]	王春香, 毛经中. 在Δ≤3的图中上独立数和上无赘数的关系[J]. 数学物理学报, 2004, 4(6): 714-716.