单圈图的D(2)-点和可区别全染色

图G的D(2)-点和可区别全染色是指在图G的一个正常全染色φ下,G中任意两个距离不超过2的顶点u,v,其色集合中所有颜色数之和互不相同.使得G有一个k-D(2)-点和可区别全染色的最小整数k,称为图G的D(2)-点和可区别全色数.文中应用组合零点定理和权转移方法刻画了单圈图的D(2)-点和可区别全染色,并得到其D(2)-点和可区别全色数.

一类仙人掌图的D(2)-点可区别全染色

用数学归纳法和组合分析法给出最大度为3的仙人掌图G T的D(2)-点可区别全染色,进而得到χ_(2vt)(G T)≤6.结果表明,D(β)-VDTC猜想对最大度为3的仙人掌图成立.

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义My-cielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}。讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。

图的D(2)-点可区别一般边染色

引入了图的D(β)-点可区别一般边染色,并对β=2的情形做了讨论,得到了路,圈,星,双星,扇,轮的D(2)-点可区别一般边色数,对于2距离色数等于3及4的图的D(2)-点可区别一般边色数做了探讨,特别研究了具有稳定2距离4着色的图的D(2)-点可区别一般边染色.文中提出了一个相关猜想和一个公开问题.

图的D(b)-点强可区别的全染色

提出了图的D(b)-点强可区别的全染色的概念并给出了几个基本定理,通过穷举法和组合分析法研究了b=2时,路图的具体染色,最后提出了一个猜想.

广义Mycielski图M_n(P^3_m)的D(β)-点可区别正常全染色

单图G的D(β)-点可区别正常全染色是指图的距离不超过β的任意两点的色集合都不同的正常全染色,所谓两点u,v间的距离是指这两个点之间的最短路的长,记为d(u,v).D(β)-点可区别正常全色数是对图G进行D(β)-点可区别正常全染所需最小色数.给出了当β=1,2时广义Mycielski图Mn(P3m)的D(β)-点可区别正常全色数.

蛛形图的D(3)-点可区别的全染色

利用穷举法和组合分析法讨论了蛛形图的D(3)-点可区别的全染色,得到了蛛形图的D(3)-点可区别的全色数.

蛛形图的D(2)-点强可区别的全染色

通过分析蛛形图的结构和计算它的组合度,利用穷举法和组合分析法研究了蛛形图的D(2)-点强可区别的全染色.通过构造具体染色,得到了蛛形图的D(2)-点强可区别的全色数.

(P^2)_n和(P^3)_n的D(3)-点可区别全染色

图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用,随着计算机和通讯、电力网络的日益发展,染色问题成为近年来图论研究的热点.图的D(β)-点可区别全染色又是染色问题中的难点.通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.讨论了幂图Pkn(k=2,3)的点可区别全染色,使得距离不大于3(D(3))的任意2点都有不同的色集合,得到幂图Pkn(k=2,3)的D(3)-点可区别全染色数.

蛛形图的D(3)-点可区别的边染色

蛛形图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配有重要的指导作用.利用穷举法和组合分析法讨论了蛛形图的D(3)-点可区别的边染色,得到了蛛形图的D(3)-点可区别的边色数.

D(β)-点可区别I-全染色的上界研究

设G是简单图,若图G的全染色f满足:①uv,vw∈E(G),有f(uv)≠f(vw);②uv∈E(G),u≠v,有f(u)≠f(v);③u,v∈V(G),0<d(u,v)≤β时,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv)|uv∈E(G),则称f是图G的一个k-D(β)-点可区别I-全染色。用概率方法得到了邻点可区别I-全色数的一个较小上界,并研究了若干Cartesian积图的D(β)-点可区别I-全色数的上界。

广义Mycielski图的D(β)-点可区别VIE-全染色

单图G的D(β)-点可区VIE-全染色是满足当u,v∈V(G),0<d(u,v)≤β时,有S(u)≠S(v)的正常全染色,这里d(u,v)是任意两点u,v间的距离,S(u)是点u的色集合。D(β)-点可区别VIE-全色数是对图G进行D(β)-点可区别VIE-全染色所需最小色数。文中给出了当β=1,2时广义Mycielski图Mn(C3m)的D(β)-点可区别VIE-全色数。

两类联图的D(2)-点可区别的全染色

通过对联图S_n∨S_n和F_n∨F_n的D(2)-点可区别的全染色问题的研究,进一步验证了D(β)点可区别的全染色的猜想.利用构造和穷染的方法,给出了图S_n∨S_n和F_n∨F_n的D(2)-点可区别的全染色,得到了图S_n∨S_n和F_n∨F_n的D(2)-点可区别的全色数.

双圈图的D(2)-点可区别边染色

图G的一个正常k-边染色f满足对■u,v∈V(G),当d(u,v)≤2时都有S_(f)(u)≠S_(f)(v),其中S_(f)(v)={f(vw)|vw∈E(G)}表示顶点v的所有关联边上所染颜色构成的集合,则称f为图G的k-D(2)-点可区别边染色(简记为k-D(2)-VDEC),将其所需要颜色的最小数k称为D(2)-点可区别边色数,简记为χ’_(2-vd)(G).结合Hall定理证明了最大度为△(G)的双圈图G都有χ’_(2-vd)(G)≤△(G)+2.

星和扇上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义Mycielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}.在这篇文章里,我们讨论了星和扇上的锥的D(2)-点可区别的正常边染色,并给出了相应色数.

单圈图的D(2)-点可区别边染色

用数学归纳法、反证法及构造具体染色函数法,并结合Hall定理讨论单圈图的D(2)-点可区别边染色,并给出其确切的D(2)-点可区别边色数.

P_2×P_n(n≡0(mod 4))的邻点可区别Ⅰ-均匀全染色

讨论笛卡儿积图P_2×P^n当n≡0(mod 4)时邻点可区别Ⅰ-均匀全染色问题,根据该类图的结构性质,通过构造法给出它们的邻点可区别Ⅰ-均匀全染色方法,从而有效地确定了其邻点可区别Ⅰ-均匀全色数为4.

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C’(u)≠C’(v),其中C’(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为χ’_r(G)文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题通过逐层染色的方法,得到了树的D(2)和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.

关于θ-图的邻点可区别全染色

u,v两点间连三条内部不相交的路且至多有一条长度为1的图,称为θ-图.设G是阶至少为2的连通图,k是正整数,f是V(G)∪E(G)到{1,2,3,…,k}的映射,对任意u∈V(G),记C(u)={f(u)}∪{f(uv)｜uv∈E(G),v∈V(G)}.如果:1)对任意uv,vw∈E(G)u≠w,有f(uv)≠f(vw);2)对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);3)对任意uv∈E(G),有C(u)≠C(v),那么称f为G的k-邻点可区别全染色(简记为k-AVDTC),称min{k｜G有k-邻点可区别全染色}为G的邻点可区别全色数,记作χat(G).本文得到了θ-图的邻点可区别全染色.

图的邻点强可区别的Ⅵ-全染色

提出了图的邻点强可区别的Ⅵ-全染色的概念,即:AST-Ⅵ-染色,并讨论了它的基本性质及路、圈、完全二部图、完全图、树、3-正则图的邻点强可区别的Ⅵ-全色数.