Pkn(k≡2(mod3))的D(2)-点可区别全染色

图的D(β)-点可区别全染色就是指图G的一个正常全染色且使得距离不大于β的任意两点有不同的色集合.讨论了幂图P_n~k当k≡2(mod3)时的D(2)-的点可区别全染色,并且根据P_n~2与C_n~2图的结构关系获得C_n~2的邻点可区别的全染色数.     

一类正则循环图的Cartesian积图的D(β)-点可区别VI-全染色及I-全染色

设G是简单图,若图G的全染色f满足:1)(?)uv,vw∈E(G),有f(uv)≠f(vw);2)(?)uv∈E(G),u≠v,有f(u)≠f(v);3)(?)u,v∈V(G),0相似文献   

一类正则循环图的Cartesian积图的D(β)-点可区别Ⅵ-全染色及Ⅰ-全染色

设G是简单图,若图G的全染色f满足:1)(V)uv,vw∈E(G),有f(uv)≠f(vw);2)(V)uv∈E(G),u≠v,有f(u)≠f(v);3)(V)u,v∈V(G),0＜d(u,v)≤β,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv) |uv∈E(G)}.则称f是图G的一个D(β)-点可区别Ⅰ-全染色.若f只满足条件1)和3),则称f是图G的一个D(β)-点可区别Ⅵ-全染色.研究了当β=1,2时一类正则循环图与圈的Cartesian积图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数,并讨论了正则图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数的上界.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

C_m·S_n的D(2)-点可区别边色数

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点u,v之间的最短距离.得到了Cm.Sn的D(2)-点可区别边色数.     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

M(C_n)和M(W_n)图的邻点可区别的Ⅰ-全色数

研究了M(C_n)和M(W_n)图的邻点可区别的I-一全染色.根据M(C_n)和M(W_n)图的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k)的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

D(2)-点可区别正常边色数的一个上界

图G的D(β)-点可区别正常边染色是指G的一个正常边染色f使得对任意两点u,v∈V(G),0相似文献   

图的邻点可区别Ⅵ-全色数和邻点可区别E-全色数

利用穷染、递推的方法讨论了路、圈、完全图、轮和扇的邻点可区别Ⅵ-全染色.并用概率方法研究了一般图的邻点可区别E-全染色,给出了图的邻点可区别E-全色数的一个上界.即δ≥7且△≥28,则有x_(at)~e(G)≤10△,其中δ是图G的最小度,△是图G的最大度.