Ramsey重数研究  

Ramsey Multiplicities of Some Graphs

作　　者：邵泽辉[1,2] 王子成[2] 张凯[2] 

机构地区：[1]成都大学信息科学与技术学院,四川成都610106 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《武汉大学学报（理学版）》2009年第6期629-632,共4页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金资助项目(60533010);国家高技术研究发展计划(863)项目(2006AA01Z104)

摘　　要：对于图G1,G2,2色广义Ramsey数R(G1,G2)表示满足下列条件的最小正整数p:如果用2种颜色中的一种对Kp的每一条边染色,总有Kp的一个子图同构于Gi,它的边都染有第i种颜色,1≤i≤2.对KR(G)的所有可能的边2-着色中,含有单色子图G的最少的个数称为图G的重数.利用计算机计算了若干不小于5阶图的Ram-sey重数精确值:M(C6)=10,M(P6)=300,M(P7)=720;当计算量很大时,利用模拟退火算法得到了若干Ramsey重数的上界:M(B4)≤51,M(K2,4)≤24,M(K3,3)≤150,M(K2,5)≤47,M(W6)≤34,M(B5)≤48.For given graphs G1 and G2, the 2-color Ramsey number R（G1 ,G2） is defined to be the least positive integer p such that every 2-coloring of the edges of complete graph Kp contains a monochromatic copy of Gi colored with i, for some 1≤i≤2. We obtained some exact values by computer, M（C6）=10,M（P6 ）= 300 ,M（P7）= 720. When the computation complexity is high for exact values, we computed some upper bounds of Ramsey multiplicities by simulated annealing method ：M（B4）≤51 ,M（K2,4）≤24,M（K3,3）≤150 ,M（K2,5 ） ≤ 4 7 ,M（W6 ）≤34 ,M（B5 ）≤48.

关 键 词：RAMSEY数 Ramsey重数 边着色 

分 类 号：O157.5[理学—数学]