三色Ramsey数R(Cm1,Cm2,Cm3)研究

用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得对所有的1≤i≤r都满足Hi Gi,则称图G对于(H1,H2,…,Hr)可r着色.R am sey数R(H1,H2,…,Hr)是使得完全图Kn对于(H1,H2,…,Hr)不可r着色的最小正整数n.令m1>m2≥m3,E r.do.s等给出了当m1足够大时R(Cm1,Cm2,Cm3)的值.通过对m1不是足够大的情况进行研究,证明了当m≥5时,R(Cm,C3,C3)=5m-4;并给出了当m1≤7时R(Cm1,Cm2,Cm3)的值.     

三色拉姆塞数R3(C8)研究

用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得每一个Gi(1≤i≤r)都不包含图H,则称图G对于H可以r着色.拉姆塞数Rr(H)是使得完全图Kn对于H不可以r着色的最小正整数n.令Cm表示长度为m的圈,Dzido等证明了R3(C2k)≥4k.本文对k=4的情形进行研究,利用计算机,通过大量的计算证明了R3(C8)=16.     

全着色边临界图的一个注记

研究了全着色边临界图的结构，证明了对于△≥5的全着色边临界图G（V，E），若u∈V（G），d（u）=3，uvi∈E（G）（i=1，2，3），则△-1≤d（vi）≤△．     

二分图中具有正交(g,f)-因子分解的子图

设G是一个二分的(mg+k,mf-k) 图,其中1≤k相似文献   

(k(f-1)+r-1,kf-r+1)-图的均匀边着色

通过研究因子分解,证明了:对于(k(f-1)+r-1,kf-r+1)-图G(2≤r≤k),H是G中一个给定的有r条边的子图,则G存在一个子图R,使得R有一个均匀边着色与H近似正交.     

R（n，1×m）型图的L（3，2，1）-标号

文章给出了当n≤7时,R（n,1×m）型图的L（3,2,1）-标号数λ3,并提出当n≥8时,R（n,1×m）型图的L（3,2,1）-标号数λ3的猜想．     

图中含有给定圈的正则因子存在性度条件

设n和r是正整数使得r≥n＋1≥4．一个图被称为K1,n-free图，如果它不含导出子图K1,n。证明了：若G是一个有圈H的图且r｜V（G）｜为偶数，G—E（H）是连通的K1,n-free图且G—E（H）的顶点最小度至少是（n（r＋1）-3/r-2）[rn-2/2（n-1）]-n-1/r-2（[rn-2/2（n-1）]）^2＋n-3那么G有r-因子F包含H中的所有的边．     

七圈对低阶轮的Ramsey数

给定两个图F和H,Ramsey数R（E,H）是指具有如下性质的最小正整数N：对任意的N阶图G,或者F是G的子图,或者H是G的补图的子图．令Gm表示m阶圈,Wn表示n＋1阶轮．本文证明了当8≤n≤10时,R（C7,Wn）=2n＋1．     

Ramsey数r(mC_3,nC_4)

对于图G和图H ,Ramsey数r(G ,H)定义为最小正整数 p ,使得完全图Kp 用红、蓝两色作任意边着色后 ,总含红色子图G或蓝色子图H。以mG记m个图G的不相交并 ,Ck 记长度为k的圈 ,对于正整数m、n ,n≥m≥ 1 ,本文确定了Ramsey数r(mC3 ,nC4)。     

二部图的[r，s，t]-着色

给出了二部图G的[r，s，t]-色数的界及它达到下界时的条件，讨论了星作为特殊二部图的[r，s，t]-色数，得到的结果为若G是二部图，任意v1，v2∈V△，v1v2 （∈/）E（G），任意u∈V△， u1∈NG（u），使得dG（u1）=1，且s≥2t，r≤t，则χr,s,t（G）=（△-1）s＋1；若G是二部图，且r≥（△-1）s＋2t，则χr,s,t（G）（G）=r＋1；若G是二部图，且（△-1）s＋t〈r≤（△-1）s＋2t，则χr,s,t（G）≤（△-1）s＋2t＋1；若G是二部图，则r△＋1≤χr,r,r（G）≤r（△＋1）＋1。     

书图和扇形图的Ramsey数

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,或者存在红色子图G,或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1,Fn=K1+nK2.证明了当m≥1且n≥max{2,3 m-2},R(Bm,Fn)=4n+1;当n≥38,R(F2,K2,n)=2n+3.     

笛卡尔积图P_m×P_n的IC-着色

设G是一个连通图,f个将顶点集V G对应到正整数集N的函数,对G的任意子图H,我们定义fs H=Σν∈V（H）fν。如果对任意的整数k∈Σ1,fs GΣ,存在一个G的连通子图H,使得fs H=k,则称f为图G的一个IC-着色。并定义图G的IC-指数M G为使得顶点和最大时的fs G。对两条路的笛卡尔图的IC-着色进行研究,得到了它的一个下界：对任意的2≤m≤n,有M Pm×Pn≥2m-1 2n-1。     

两类特殊的图Cm·G的（p，1）-全标号

设G为任意简单图，v∈V（G），把G拷贝m次，然后把拷贝后的m个v连成圈，所得到的新图记为Cm·G（v）．本文给出了两类特殊的图Cm·G的（p，1）-全标号．     

关于Alavi猜想的一个结果

Alavi在[1]中提出了图的升分解问题．并猜想：设G是星S1．S2．…，Sn的并图，S1有a1条边，n≤a1≤2n-2，∑j-1 ^k ai=(n 1/2)．则G可升分解为星图的并．本文证明了当a1≥n，且a1 1-a1=d(d≤S，1≤i≤k-1)时,猜想的结论成立。它可作为[2]的发展。     

围长为r的圈布图最大边数的新下界

降为n的图G的圈长分布为序列{C1,C2…,Cn},其中Ci是G中长为i的圈的数目,若图G的圈长分布满足C1＝C2＝…＝Cr-2＝0,Cr＝1,且对i＝r 1,…,n,有Ci≤1,则称图G是围长为r的圈分布图,用fr(n)表示阶为n的围长为r的圈分布图最大可能的边数,本文证明：对每个整数n≥R0（其中：r＝3时,R0=17,r≥4时,R＝3r-[r/2] 5,有fr(n)≥n-r ek t 4 η。     

关于三部图K(m,n,r)-A(|A|=2)色唯一性的几个结果

设G是简单图，用P（G，λ）表示图G的色多项式．令K（m，n，r）表示完全三部图。G=K（m，n，r）-A（｜A｜=2），3≤m≤n≤r.证明了若图Y使得P（Y，λ），则Y=K（m＋α,n＋β,r-（α＋β））-S，其中α,β是整数，且｜S｜=e=（r-m）α＋（r-n）β-2（α^2＋αβ＋β^2）≥0.且e=2时，G和Y同构，同时给出了α，β的范围。     

点可迁图的顶点划分

设G是k正则连通点可迁图。图G的一个边割S称为限制性边割，如果G－S不含孤立点，最小限制性边割所含的边数λ′称为限制性边连通度。已经证明λ′≤2k-2，等号成立时，称图G是极大限制性边连通的。本文证明了：如果G不是极大限制性边连通的，那么G的顶点集存在一个划分π＝（C1，…，Cm)，使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2，…，m，而且k≤|H|≤2k-3。     

扇形图与匹配图的临界星图Ramsey数

对于完全图Kn和一个额外的顶点v,通过在v与Kn之间添加k条边所得出的图,记为KnK1,k.设G和H是任意的图,临界星图Ramsey数r*(G,H)定义为最小的正整数k,使得图KN-1K1,k的任意红蓝2-边着色,或者存在单色的红色子图G,或者存在单色的蓝色子图H,这里N指的是Ramsey数r(G,H).文中找到了r(Fn,mK2)的所有临界图,利用这些临界图得到了临界星图Ramsey数r*(Fn,mK2)=m+1,nm≥1,以及r*(Fn,mK2)=2 m,n≤m,这里Fn=K1+nK2是扇形图.     

圈与K4的临界完全图Ramsey数

对给定的2个图G和H,Ramsey数r(G,H)是最小的正整数r,使得对完全图Kr的边任意红蓝着色或存在红色子图G、或存在蓝色子图H.临界完全图Ramsey数r_K(G,H)是最大的正整数n,使得图K_r-K_n的边任意红蓝着色或存在红色子图G或存在蓝色子图H.当正整数n≥5时,r_K(C_n,K_4)=n/2,C_n为n个点的圈.     

用有限局部环Z/2kZ上m阶斜对称矩阵构作的卡氏验证码

设R=Z/ 2kZ(k＞1),Wm(R)(m=2v 2≥4)是R上所有m阶斜对称矩阵构成的集合,WmA(R,Hr1r2)={A∈Wm(R)|PAP'=Hr1r2}是Wm(R)中一切与Hr1r2合同的斜对称矩阵构成的集合,令F=∪0≤r1＜r2≤k-1WmA(R,Hr1r2),其中Hr1r2=Dr1(◎)Δr2,Dr1=02-r1I(v)-2-r1I(v)0,Δr2=2-k-12-r2-2-r20-,v≥1,0≤r1＜r2≤k-1.利用F中矩阵构作一个Cartesian验证码,计算其全部参数.