圈——书Ramsey数

用两种颜色,比如红和蓝,给完全图K_n的边着色.把着红色的边集记为E_1,着蓝色的边集记为E_2.并把K的边集分别是E_1和E_2的生成子图分别记为R和B.这时称R和B是K_n的一个分解,记为K=R⊕B.图G_1和G_2(不一定是完全图)的Ramsey数r(G_1,G_2)是一个最小的正整数n,它使得K的任一分解K=R⊕B,有RG_1或BG_2.     

图mP2∪mCt（3≤t≤10）的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合.对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ′s(G).通过将路和圈填装到完全图,我们给出了mP2∪mCt的点可区别正常边色数的一个刻画,并利用递归染色的方式,得到了χ′s(mP2∪mCt)(3≤t≤10).     

关于Ramsey数R(3,3,4)的界

设K_n为n阶完全图,以色α_1…α_t着K_n的边。又以E_i表示K_n中着色α_i的边集,G(E_i)表示以边集E_i生成的部分图。如果有一着色方案,使得每一G(E_i)不包含l_j阶完全子图K_(li)(1≤i≤t)则称K_n为可(K_l_1,…,K_l_t)——着色图。记R(l_1,…,l_t)=max{n 1:K_n为可(K_l_1,…,K_l_t)——着色图}并称R(l_1:…,l_t)为关于参数l_1,…,l_t的Ramsey数。     

关于Ramsey数R(1,m)与R(k,l,m)的下界

设Kn为n阶完全图,以t种颜色∝_t,…,∝_t给Kn的边着色,又设Ei为Kn中着∝_i色的边集,G(Ei)表示由Ei生成的部分图如果有某一种着色方法,使得对每-G(Ei)均不包含l_i阶完全子图K_li,那么称Kn为可(l_1,…,l_t)——着色图。记R(l_1,…,l_t)=max{n 1:Kn为可(l_1,…,l_t)——着色图}并称R(l_1,…,l_t)为关于参数l_1,…,l_t的Ramsey数。虽然,在[3]和[4]中给出一些界和递推式,但是,本文的结果所给的下界要比它来的     

两类8点8边图的图设计

设λKv是v阶λ重完全图,G是一个有限简单图.图设计(v,G,λ)-GD是一个有序对(X,B),其中X是完全图Kv的顶点集合,B是λKv中与G同构的子图(叫做区组)的集合,使得Kv中任意一条边恰出现在B的λ个区组中.研究了两类8点8边图Gi(i=1,2)的图设计,并给出了(v,Gi,1)-GD(i=1,2)的存在谱.     

图K2,3+e的最优覆盖

设λKv是λ重V点完全图，G为一个无弧立点的有限简单图，λKv的一个G-覆盖设计，记为（v,G,λ）-CD，是指一个对子（X，D），其中X为点集，D为λKv的一些子图（亦称为区组）构成的集合，使得任一区组均与G同构，且任意两个不同点组成的边至少在D的λ个区组中出现，讨论了两类六点七边图Gi=K2,3 e(i=1,2)的最优覆盖的存在性问题，证明了存在（v,Gi,λ）-OCD，i=1,2当且仅当v≥6，除去非最优（但为最大）的C（6，G1，1）=4。     

一类特殊图k-限制边连通度

设F?E (G)为图G=(V,E)的一个边集,如果G-F不连通且G-F的每一个连通分支都至少有k个顶点,F就称为图G的一个k-限制性边割.图G的k-限制边连通度是图G的最小k-限制性边割的基数,记为λk(G).限制性边连通度是衡量网络可靠性的重要参数之一.证明了在2≤k≤n,h≤n/2的情况下,一类特殊图—蜻蜓网络D(n,h)的k-限制边连通度是■     

七点有向θ图的图设计

设Kv是一个v点的有向完全图,G是一个简单有向图,Kv的一个G-设计,记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的点集,B为Kv的一些子图(也称为区组)构成的集合,使得任一子图(区组)与G同构,且Kv的任意两个不同点组成的有向边恰在B的一个区组中出现。研究了七点有向图的图设计的存在性问题。     

关于两个六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了两个六点八边图G1和G2的图设计存在性问题,并证明了(v,Gi,1)-GD(i=1,2)存在的必要条件v≡0,1(mod 16)且vE 16也是充分的.     

Ln,p图的代数连通度

Kp表示p阶完全图.选取Kp的任意r个顶点分别点粘接r棵树,得到n阶图Ln,p.所有n阶图Ln,p的集合记为（L）n,p.代数连通度是刻画图的连通性的重要参数,笔者分别确定了Ln,p中具有最大、最小和第二小代数连通度的图.     

Δ(G)=2的图的孪生强边染色

设σ是一个阶至少为3的简单连通图G的k-正常边染色,其中颜色集合为{0,1,2,…,k-1}.若对任意距离不超过2的两条边e,,存在σ(e)≠σ(),则称σ为G的强边染色.若图G的强边染色σ能够诱导一个G的2-距离点染色,则称σ是G的孪生强边染色.最少的颜色数为G的孪生强边色数,记为■_(s,t)(G).通过研究简单连通图的孪生强边染色,得到了相应的染色数.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

六点有向θ图设计

设Kv是一个v点的有向完全图,G是一个简单有向图。Kv的一个G-设计（记为（v,G,λ）-GD）是指一个二元组（X,B）,其中X为kv的点集,B为Kv的一些子图（也称为区组）构成的集合。任一子图（区组）与G同构,且Kv的任意两个不同点组成的有向边恰在B的一个区组中出现。本文研究了不同构的六点有向θ图设计的存在性问题。     

5色K_4问题的推广

设Kn是具有n个顶点的完全图,fr（n）是满足下列条件的最小正整数：对于任意的正整数m≥fr（n）,存在Kn的一个m边着色,使得Kn中的任一个Kr至少含r（r-1）/2-1种颜色.确定fr（n）的问题称为n阶完全图的r（r-1）/2-1色Kr问题（4≤r≤n）.给出了f5（n）的上界.关于14色K6问题的充要条件和f6（n）的下界.同时证明了f6（7）=19,f6（8）=26,f6（9）=33;f7（n）=n（n-1）/2-[n/4];fr（n）=n（n-1）/2-1（8≤r≤n）.     

一类六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了一类六点八边图中尚未解决的3个图Gi(i=1,2,3)的图设计存在性问题,并证明了(v,G,1)-GD(i=1,2,3)存在的必要条件v=0,1(mod 16)且≥16也是充分的.从而给出了这类六点八边图图设计存在的完全解.     

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

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

mPn 的顶点被多重色集合可区别的一般边染色

简单图 G 的一个一般边染色是指若干种颜色关于图 G 的所有边的一个分配,不要求相邻的边被分配不同的颜色。设 f是 G 的使用了 k 种颜色的一般边染色,若对u,v∈V（G）,u≠v,都有与 u 关联的边的颜色构成的多重集合异于与 v 关联的边的颜色构成的多重集合,那么称 f是使用了 k 种颜色的顶点被多重色集合可区别的一般边染色。对 G 进行顶点被多重色集合可区别的一般边染色所需的颜色的最少数目记为 c（G）,并且称 c（G）为图 G 的顶点被多重色集合可区别的一般边色数。讨论了 m 个 Pn 的点不交的并 mPn 的顶点被多重色集合可区别的一般边色数。     

完全二部图K_(3,n)(3≤n≤17)的点可区别E-全染色

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

乘积图与正则图的满着色

图G=(V，E)的一个正常着色就是将G的顶点划分为独立集，或称之为色类，记为П=|V1，V2，…VK|．对于任一色类Vi中的点v，如果它与其余色类中至少一个点相邻，则”被称为是满色的．如果在一个正常着色中，所有点都是满色的，则称这样的着色是满着色．如果一个图存在满着色，定义图的满着色数为使得图存在满着色的最小颜色数，记为xf(G)．另外，记f(G)为使图存在满着色的最大颜色数．在这篇文章中，我们研究了一些乘积图的满着色，得出一些关于正则图的满着色的结果．