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种邻点可区别染色之间的关系.     

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种邻点可区别染色之间的关系.     

K1,5,p和K1,6,p的点可区别的IE-全染色及一般全染色

利用色集事先分配法、构造染色法和反证法,探讨了完全三部图K_1,5,p和K_1,6,p的点可区别IE-全染色和点可区别一般全染色问题,确定了K_1,5,p和K_1,6,p的点可区别IE-全色数和点可区别一般全色数.     

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)给出的一个公开问题．     

关于图的边着色的一个猜想

若G是简单图,v(G)是偶数,χ'(G)=?(G)+1,则存在点v∈V(G),使χ'(G-v)=χ'(G)=?(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ'(G)=?(G)+1;(2)设G是连通图,κ'(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k2),v(G)=2n+2,χ'(G)=?(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ'(G)=?(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ'(G)=?(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)d(u)k外,其它顶点的度都等于k,χ'(G)=?(G)+1;此猜想也是成立的.     

完全图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)的一些点脆弱性参数.     

基回数为2的自中心图

Buckley 指出找寻自中心图的特征是一个困难的任务.作为这一工作的开始,找出一些自中心图类看来非常必要.文[1]定理3中证明当 k=■或 n≤k≤[(1/2)n(n-1)]时,n 个顶点 k 条边的自中心图存在.本文建议以基回数为出发点构造自中心图,并确定了基回数为2,即 k-n=1的全部自中心图.本文还纠正了[1]中的一个疏忽.设 G=(V,E)是简单图,u,v∈V(G),d(u,v)为 u,v,两点的距离.定义1 图 G 的半径 r(G)=(_{(v,w)}定义2 图 G 中顶点“的最远距离     

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

设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(θ)是二或三点着色．这个结论给出了一个判定无割边三正则图是三边着色的方法。     

列表双临界图（英文）

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的选择数,还证明了完全图是唯一的列表双临界图.     

Fourier变换的加权模不等式(英文)

给定 p,q 满足10及(有限)数列{a_k}成立,其中,k=(k_1,k_2,…,k_n),E_k~r是立方体{x=(x_1,x_2,…,x_n):k_mr≤x_m<(k_m+1)r,m=1,2,…,n}。本文还考虑了 Fourier 变换的弱型加权模不等式,给出了一必要条件。作为应用,我们给出了 Fonrier 级数的L~p[-π,π]范数估计。     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

G---的平面性

设G是一个简单图,其全图G 是以V(G)∪E(G)为顶点集的图,其中顶点x和y相邻当且仅当下面的一个条件成立: (i) x,y∈ V(G) ,且x和y在G中相邻, (ii) x,y∈ E(G) ,且x和y在G中相邻, (iii) x和y分别属于V(G)和E(G) ,且它们在G中关联. G---是全图的补图.在这篇文章中,证明了G---是平面的充要条件是 V(G) ≤ 3或者G同构于2K2,C4, K4- e,K4, 2K1 K3, K1,4, K1 K1,3,2K1 P3.     

Ramsey重数研究

对于图G_1,G_2,2色广义Ramsey数R(G_1,G_2)表示满足下列条件的最小正整数p:如果用2种颜色中的一种对K_p的每一条边染色,总有K_p的一个子图同构于G_i,它的边都染有第i种颜色,1≤i≤2.对K_(R(G))的所有可能的边2-着色中,含有单色子图G的最少的个数称为图G的重数.利用计算机计算了若干不小于5阶图的Ramsey重数精确值:M(C_6)=10,M(P_6)=300,M(P_7)=720;当计算量很大时,利用模拟退火算法得到了若干Ramsey重数的上界:M(B_4)≤51,M(K_(2,4))≤24,M(K_(3,3))≤150,M(K_(2,5))≤47,M(W_6)≤34,M(B_5)≤48.