单圈图的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的仙人掌图成立.

一些特殊图的中间图的2-距离和可区别全染色

为了进一步研究图的2-距离和可区别全染色问题,根据中间图的构造特点,通过构造染色函数,利用组合分析法得到了路,圈,星,扇,轮,双星以及轮环图的中间图的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)-点强可区别的全染色

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

子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色,且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值,记作χ′_(2-snd)(G).采用反证法证明了:若图G是子立方图,则χ′_(2-snd)(G)≤7.

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

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

两类联图的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)-点可区别的全色数.

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

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

路和圈上的锥的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时,路图的具体染色,最后提出了一个猜想.

2-连通外平面图的邻点可区别全染色

运用数学归纳法及换色技巧,探讨了Δ(G)=7的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)-点可区别的全色数.

若干倍图的2-距离和可区别全染色

为了研究图的2-距离和可区别全染色问题,根据倍图的结构特点,通过组合分析法和构造染色函数法,得到了路、圈、星、扇、轮、完全二部图的倍图的2-距离和可区别全色数.

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)-点可区别正常边染色

设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)-点可区别边色数.