Ramsey定理的一种推广

Ramsey定理指出:对于任何一个正整数k,存在一个最小的正整数r(k,k),使得对任意一个至少有r(k,k)个顶点的图G,它或者有k个顶点的完全子图Kk,或者有k个顶点是独立集.由此定理易得:设G是顶点数n>r(k,k)的简单图,其边数e>0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e>0,对某个给定的自然数k(2≤k≤n-2),若G的所有k阶导出子图的边数相等,则G是完全图.     

加强超立方体中条件容错圈

研究了条件容错模型下n维加强超立方体Qn,k的结构性质,设Fv表示故障点的集合,Fe表示错误边的集合,且Fv=f_v,Fe=f_e.若Qn,k(n≥4,1≤k≤n-1)满足约束条件:1)f_v+f_e≤2n-4和2)Qn,k中每个点至少关联两条无故障边时,Qn,k-Fe-F_v中含一个长度至少为2n-2f_v的圈.同时证明了当Qn,k(n≥5,1≤k≤n-1)满足约束条件:1)f_e+f_v≤2n-3,f_e≥k和2)每个节点至少关联两条无故障边时,Qn,k中能嵌入一条长为2~n-2f_v的容错圈.     

圈的笛卡积的圈点连通度（英文）

设G是一个点集为V(G),边集为E(G)的图.对于图G的点子集S,如果G-S不连通并且至少两个连通分支包含圈,则称S为一个圈点割.如果一个图有圈点割,称该图为圈可分离的.一个圈点可分离图G的最小圈点割的阶数被称为圈点连通度,记作κ_c(G).文章证明了κ_c(C_3□C_(n1)□Cn_2□···□C_(nk))=6k和κ_c(C_(n1)□C_(n2)□···C_(nk))=8k-8,其中对于i=1,2,···,k,Cni是一个长度大于等于4的圈.     

一致最可靠完全多部图

对于一个连通图G,假设边是可靠的而点以P的概率相互独立地发生故障.图G不连通的概率是一个多项式P(G,p).记作Ω(n,m)是有n个点,m条边的连通图的集合.如果对于任意的网H ∈Ω(n,m)和任意实数p ∈[0,1],P(G,p)≤P(H,p)成立,则称G是Ω(n,m)中的一致最可靠图.本文证明了完全k部图K(b,(b+1)k-3,(b+2)2)是它所在的类中的一致最可靠图.另外,还证明了对任意的h≥2,K(bh,(b+1)k-h-1,(b+2)1)不是其所属类中的一致最可靠图.     

Cartesian积与邻点可区别着色之间的关系（英文）

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

几类特殊图的优美性

证明了对任意大于1的自然数n,p,当m≥2p＋2时,非连通图Fm∪Kn,p和Fm,2 m∪Kn,p是优美图;当m≥3时,图Fm∪St（n）是优美图;当m≥4,图Fm,2 m∪St（n）和Fm,2 m∪Gr是优美图.     

完全图Kronecker积的一些点脆弱性参数(英文)

设G1和G2是两个图.G1和G2的Kronecker积G1×G2具有顶点集V(G1×G2)=V(G1)×V(G2),边集为E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1)且u1u2∈E(G1)}.在本文中,我们确定了两个完全图的Kronecker积Km×Kn(n≥m≥2且n≥3)的一些点脆弱性参数.     

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

图G的一个E-全染色是指使相邻点染以不同的颜色,且每条关联边和它的端点染以不同的颜色的全染色。对图G的一个E-全染色f,一旦对图G中任意互不相同的两点u, v,有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,那么f称为图G的点可区别的E-全染色,简称为VDET染色。令χ_(vt)~e(G)=min{k|G存在k-VDET染色},称χ_(vt)~e(G)为图G的点可区别E-全色数。运用分析法和反证法,讨论并证明了完全二部图K_(10,n)(215≤n≤466)的点可区别E-全色数。     

复合图点列表着色的可选性

r部完全图Km*r是完全图Kr与空图Sm的复合图Kr[Sm] . Erdo。s P, Rubin A L和Taylor H在[1]提到了确定Kr[Sm]的点列表着色的可选性的问题并证明了ch(Kr[S2]) = r .Kierstead H A[2]证明了ch(Kr[S3]) =[(4r - 1)/3] .假定Gm是圈Cn与空图Sm的复合图Cn[Sm] .考虑了Gm的列表着色的可选性并证明了ch(G2) =3, ch(G3)≤ 4及在n是奇数时, ch(G3) = 4 .     

代数多项式的点态同时逼近

设N={1,2,…},r∈N U{0}C~r是[-1,1]上具有r阶连续导数的实值函数全体组成的空间,f∈C~r的范数规定为||f||= (?)|f(x)|.记Ⅱ_n是阶数不超过n的代数多项式全体组成的集合.c是不依赖于n的正的绝对常数,在不同的地方.可以是不同的地方,可以是不同的值.对于f∈C~r,k∈N,w_k(f,t)是f的k阶连续模.又记△_n(x)=(1-x~2)~(1/2)/n+(1/n~2),δ_n(x)=(1-x~2)~(1/2)/n.谢庭藩在我国第二次逼近论会议上提出下述问题: 问题X 是否对于给定的自然数k和r,都有映C_r为Ⅱ_n.线性算子L_(n,k,r),使得对于任意的函数f∈C~r,成立不等式     

无割边三正则图三边着色的一个充分必要条件

设G是无割边三正则图，θ={C1，C2，…，Ck)是G一个圈覆盖，定义一新图G(θ)=(V，E)，这里V={C1，C2，…,Ck)，(Ci，Cj)∈E当且仅当E(Ci)∩E(Cj)≠φ(1≤i≠j≤k)．那么G是三边着色的充分必要条件是G有一个圈的一或二次覆盖θ并且G(θ)是二或三点着色．这个结论给出了一个判定无割边三正则图是三边着色的方法。     

Cm□Cn的支撑树的一些性质

积图G1□G2是一个以笛卡儿积V(G1)×V(Gt)作为其点集．其中点(u,v)点(x,y)相邻当且仅当u=v且v与y在G2中相邻,或者v=y且u与z在G2相邻．证明了对图Cm□Cn的任意支撑树T,其中m和n不全为偶数,总存在一条Cm□CnT之外的边,添加到T上形成一个长度至少为m n-1的圈．这解决了陈(Dis-creteMathemstics 287(2004)11-15)给出的一个公开问题．     

关于丢番图方程f(x)=yn-1/y-1的解

丢番图方程f(x)=yn-1/y-1是一种很重要的且引人注目的指数丢番图方程.用初等方法证明了,若f(x)=(g(x))2 a,a∈Q,这里g(x)是系数的最大分母为k的有理系数多项式,2r‖k,则该方程在2n时的解(x,y,n)必满足y＜max{k/23 r((n 1 (n 1)/2),n-5√k2a2},从而给出了该类方程的解的上界,改进了参考文献中的一些结果.     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

k—唯一可着色图的一个问题

Bollobas.B在[1]中提出如下问题,对于k≥3,确定u_k(n)的阶。其中u_k(n)=min{m:存在G(n,m),G(n,m)是k一唯一可着色图}。特别是改善平凡的不等式至今还不知道是否存在     

偶匹配可扩图的度和连通度条件(英文)

称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.     

分数临界图的新韧度条件（英文）

一个图G称为分数(g,f,n)-临界图如果满足从G中删除任意n个顶点,其剩余子图依然存在分数(g,f)-因子.得到分数(g,f,n)-临界图的新韧度条件,若t(G)≥b2-1-Δ+bn/a,则G是分数(g,f,n)-临界图,其中Δ=b-a.进一步地,给出分数(a,b,n)-临界图的韧度条件.     

对换网络的可系性（英文）

G是一个图,k是一个正整数,u,v是G中任意两个不相同的点,u与v之间的一个k-container C(u,v)指的是从u到v的k条内部点不交的路的集合.并且C(u,v)被称作是k*-container,如果它包含G中所有的点.图G是k*连通的(或者说k生成连通的),如果对于G中任意两个不同的点u,v都存在u到v的一个k*-container.一个二部图G是k*可系的,如果对于来自不同部分的任意两个点u,v都存在u到v的一个k*-container.在这篇文章中我们证明了n阶对换网络TNn是(C2n)*可系的.     

关于丢番图方程f(x)=的解

 丢番图方程f(x)=yn-1/y-1是一种很重要的且引人注目的指数丢番图方程.用初等方法证明了,若f(x)=(g(x))2+a,a∈Q,这里g(x)是系数的最大分母为k的有理系数多项式,2r‖k,则该方程在2n时的解(x,y,n)必满足y＜max{k/23+r((n+1 (n+1)/2),n-5√k2a2},从而给出了该类方程的解的上界,改进了参考文献中的一些结果.