关于Ramsey图:一个递归型查找图中所有给定元素个数独立集的算法

改进了作者在文献〔1〕中给出的算法 ,给出一个速度较快的新算法 ,对一个可能的 ( s,t,n) -Ramsey图 ,该算法可以找出其中所有给定元素个数的独立集 ,进而可以检验该图是否是一个 ( s,t,n) -Ramsey图 .

(3,11,45)-Ramsey图的递阶构造(英文)

给出了10-正则循环(3,11,45)-Ramsey图的一个递阶生成构造.该正则循环图的弦长序列是:1,3,5,12,19.同时证明了拉姆赛数R(4,5) 46.进一步,我们发现了一个有趣的结果,作为(3,11,45)-Ramsey图的一个子图(3,10,38)-Ramsey图,改变(3,10,38)-Ramsey图的4条Ramsey临界边,该图将变为另一个10正则的循环(3,10,38)-Ramsey图.该正则循环图的弦长序列也是:1,3,5,12,19.

自补图与Ramsey图

讨论了自补图的构造方法、自补图与Ramsey图的关系 ,给出了顶点数不超过 1 0 1的所有含 4m

对Ramsey图(3,10)的初步探讨

用二色图的递阶生成方法,充分讨论了K39(3,10)的构造,并推想该图是(3,10)Ramsey图.

利用二进制数算法寻找5个点的Ramsey图

用二进制数来表示完全图的各种组合,借助计算机编程可从完全图的各种组合中寻找出ramsey图。5个顶点的Ramsey图是最基本的Ramsey图,这种基本方法为寻找更复杂的Ramsey图提供了基础。

临界完全图Ramsey数

设G和H是任意的图,Ramsey数r(G,H)定义为最小的正整数r,使得图K_r的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.临界星图Ramsey数r_*(G,H)为最小的正整数n,使得图K_r-K_(1,r-1-n)的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.在临界星图启发下,临界完全图Ramsey数r_K(G,H)定义为最大的正整数n,使得图K_r-K_n的任意红蓝二边着色或存在单色的红色子图G或存在单色的蓝色子图H.这里r为Ramsey数r(G,H).确定了r_K(W_(1,n),K_3)和r_K(C_n,K_3),其中W_(1,n)=K_1+C_n为轮.

生成二色Ram sey图R(3,p)的基本元方法

构造二色 Ramsey极图其复杂度是 NP完全难的问题 .通过生成 Kn( 3,p)阶图 (见文献〔 1〕)以期获得阶最大极图 R( 3,p) ( Kn( 3,p)≤ R( 3,p) =r( 3,p) -1 ) .本文给出了一种生成Ramsey图 R( 3,p)

含双参数的Ramsey数新上、下界公式(英文)

本文得到了含双参数x,y的Ramsey数的新上、下界公式,且初步研究了它的应用,证明了R(K6-e,K6)≤116和R(K6-e,K7)≤202.

一个查找二色Ram sey图中可能存在的自由边的算法(英文)

Kn( s,t)定义为一个正整数 n,同时存在一个由二色边构成简单完全图 Kn,使得 Kn中既不存在单色完全子图 Ks和单色完全子图 Kt.在 Ramsey图 Kn( s,t)中一条自由边定义为 ,即使单独改变这条边的颜色 ,所得到的新图仍是一个二色 Ramsey图 Kn( s,t) .本文基于作者在文献〔2〕中给出的算法 ,提出一个新算法 ,该算法可以找出一个给定 Ramsey图 Kn( s,t)中的所有可能的自由边 ,并简要分析了其时间复杂性 .对于一个已有的 Ramsey图 Kn( s,t) ,利用该算法可能找出其他的 Ramsey图 Kn( s,t)

Ramsey数的新上、下界公式

运用该文的上界公式对Ramsey数的上、下界公式作出了一些改进,得到了含双参数的Ramsey数的新上、下界公式,并且通过证明得到了2个Ramsey数的较好结果.

两个Ramsey数上界公式的统一与改进

该文在引入参数的基础上统一了两个Ramsey数的上界公式且对其一作了改进.

Ramsey数 r(3,q)中的新下界

我们利用计算机来构造既没有三角形又没有q个顶点的独立集的循环图。当q=14、15、16,17时,由我们构造的循环图得到Ramsey数的四个新下界: r(3,14)≥64; r(3,15)≥73; r(3,16)≥79; r(3,17)≥88。

研究Ramsey问题的计算机方法

本文阐述了一个构造Ramsey图的算法,它可以作为寻找Ramsey数(P=3)的一个辅助工具.算法采用回溯方法,搜索极大独立集组成的堆栈.并给出了寻找Ramsey数的一种具体的步骤.

经典Ramsey数R(4,16)的下界

通过构造既不含4顶点完全子图、也不含16顶点独立集的155阶循环图,证明了R(4,16)≥156.

Ramsey数r(3,q)的下界公式

本文证明了两类特殊的循环图是(3,q)-图,从而得到:当q≥4时,r(3,q)≥5*q-13;当q≥7且为奇数时,r(3*q)≥7·q-33.

关于Ramsey数R(4,17)的下界

运用计算机构造了一个既不含4顶点完全图、也不含17顶点独立集的162阶循环图,得到了Ramsey数R(4,17)的下界:R(4,17)≥163.

Ram sey数的几个新下界公式

本文建立了几个 Ｒａｍ ｓｅｙ

r(3,13)的新下界

我们利用计算机构造了一个既不含3—点团、也不合13—独立点集的59顶点循环图,从而得到了Ramsey数的一个新下界:r(3,13)≥60。