路和圈的笛卡尔积的邻点强可区别全染色

本文介绍了部分特殊图类的笛卡尔积图的邻点可区别全染色的有关重要结论,并在此基础上讨论n阶路和n阶圈的笛卡尔积Pn×Cn的邻点强可区别全染色,得到了n阶路和n阶圈的笛卡尔积Pn×Cn的邻点强可区别全然色数χast()Pn×Cn=6。     

图的一般邻点可区别色指标

给出了完全图Kn、路Pm与完全图Kn的Cartese积Pm×Kn、圈Cm与Kn的Cartese积Cm×Pn等图的一般邻点可区别色指标,并得到2维网格Mm,n2种颜色可染、2维环形网格TMm,n3种颜色可染等结论.     

几个笛卡儿积图的邻点强可区别的EI-全染色

给出了笛卡儿积图Pm×Sn,Pm×Fn,Pm×Pn,Pm×Wn,Pm×Cn的邻点强可区别的EI-全色数.     

关于图P_m×P_n的邻点可区别全染色

设图Pm×Pn(n 2,m 2)是m-路和n-路的积,给出图Pm×Pn(n 2,m 2)的邻点可区别全色数.     

联图的邻点可区别无圈边染色

根据图的邻点可区别无圈边染色的定义,利用构造的方法讨论联图Pm∨Wn、Pm∨Fn、Pm∨Pn、Pm∨Sn和Cm,n的邻点可区别无圈边染色,并给出它们的邻点可区别无圈边色数及其证明,且均满足图的邻点可区别无圈边染色猜想.     

弱直积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且任意距离不大于2的两个顶点着不同的颜色.得到弱直积图的一个2-距离色数的可达界,即Δ(G).Δ(H)+1≤χ2(G×H)≤χ2(G).2χ(H),且给出一些特殊弱直积图的2-距离色数,说明此界可达.如χ2(P2×Pn)=Δ(P2).Δ(Pn)+1=3(n≥3),χ2(Pm×Pn)=Δ(Pm).Δ(Pn)+1=5(m≥3,n≥3)说明下界可达,χ2(Km×Kn)=χ2(Km).2χ(Kn)=mn,说明上界可达.     

关于两条路的盒叉积的消圈数

讨论两条路的盒叉积的消圈数.对于一般图G1和G2,得到了它们的盒叉积G1■G2的消圈数的一个紧的上界和一个紧的下界.而对于分别含m和n个顶点的2条路Pm和Pn,得到了Φ(Pm■Pn)的准确值,即Φ(Pm■Pn)=min{m.﹂n/2」,n.﹂m/2」}.     

图P_n~2×S_m与P_n~2×F_m的一般邻点可区别边染色

简单图G的gnd-染色是指图的邻点可区别的非正常边染色.所谓邻点可区别是指G的任意两个相邻的点u,v∈V(G)有C(u)≠C(v).C(u)是点u的色集合。该文讨论了笛卡儿积图Pn2×Sm和P2n×Fm的一般邻点可区别边染色,即gnd-染色,并给出了相应色数.     

Pm×Fn及Cm×Fn的邻点可区别全色数

研究了笛卡儿积图Pm×Fn的邻点可区别全染色问题.运用构造法得到了其邻点可区别全色数,然后从图的结构关系上进一步获得了Cm×Fn的邻点可区别全色数.     

图C2m×Pn与C2m×Cn的邻点可区别非正常边染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.在这篇文章里,我们讨论了笛卡儿积图C2m×Pn和C2m×Cn的邻点可区别边非正常边染色,并给出了相应色数.     

几类弱积图的邻点可区别一般边染色

讨论了弱积图邻点可区别一般边染色,给出了P_2n×K_m,C_2n×C_2m,C_2n+1×C_2m+1,C_2n+1×K_m的邻点可区别一般边色数,得到了当G和H都无孤立边且色数均至少为3时,G×H邻点可区别一般边色数至少为3的结论.     

一类Pm×Cn图的邻点强可区别全染色

图的一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点强可区别全染色,其所用最少染色数称为邻点强可区别全色数。经证明得到了一类积图Pm×Cn的邻点强可区别色数。     

P_n~2的Mycielski图的邻强边色数和邻点可区别全色数

定义新图Pn2,并在n≥3时,确定Pn2的Mycielski图的邻强边色数和邻点可区别全色数,构造一个M(Pn2)的邻点可区别全染色法.     

路与圈的笛卡尔乘积的全控制数

令图G是无孤立点的无向图.V(G)是图G的顶点集,D是V(G)的真子集.如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集.G中最小全控制集的顶点数称为G的全控制数,记为γt(G).参考已有全控制数的知识及笛卡尔乘积Cm□Cn、Pm□Pn的全控制数的相关结论,利用γt(Cm□Cn)≤γt(Pm□Cn)≤γt(Pm□Pn)这一不等式给出了Cm□Pn(m=3,4)、Pm□Cn(n=2,4)的全控制数.     

路的3类积图的邻点扩展和可区别全染色

[目的]为了得到两条路的积图的邻点扩展和可区别全色数.[方法]直接构造了两路的笛卡尔积、直积、半强积的邻点扩展和可区别全染色.[结果]得到这3类积图的邻点扩展和可区别全色数.[结论]证明了NESDTC猜想对于两路的笛卡尔积、直积、半强积成立.     

若干联图Pm∨Gn的邻点可区别E-全染色

记χat'e(G)为图G的邻点可区别E-全色数.若Pm是m阶的路,Sn是n+1阶的星,且nm≥2,则χate(Pm∨Sn)=4;若Pm是m阶的路,Fn是n+1阶的扇,且m≥2,n≥2,则χate(Pm∨Fn)=5;若Pm是m阶的路,Wn是n+1阶的轮,且m≥2,n≥3,如果n≡0(mod 2),则χate(Pm∨Wn)=5,如果n≡1(mod 2),则χate>(Pm∨Wn)=6;若Pm是m阶的路,Kn是n阶完全图,且n≥4,m≥2,则χate+(Pm∨Kn)=n+2.     

若干强积图及合成图的邻点可区别一般边染色

讨论了若干满足某些条件的两个图的强积图以及合成图的邻点可区别一般边色数的若干结论, 并在此基础上得到了PnC2m+1, C2nFm, C2nW2m+1, PnFm, PnW2m+1, C2n+1C2m+1, Pn［C2m+1］, C2m+1［Pn］, C3［C2m+1］, C2m+1［C3］ 等图类的一般邻点可区别边色数。     

梯图L_m(2<m≤37)的点可区别全染色

利用三角排序证明了当2m≤37且C4n-1/2+2m≤C4n/2+2时,梯图Lm≌Pm×P2的点可区别全色数为n.     

K2n-1×K2n+1’的邻点可区别全染色

基于完全图的全染色和邻强边染色,得到了相邻奇数阶完全图的直积图K2n-1×K2n+1’的邻点可区别全色数χat(K2n-1×K2n+1’)=4n(n为正整数).     

星图S5及5个六阶图与路的笛卡儿积图的交叉数

两个图G1和G2的笛卡尔积图G1×G2是这样一个图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1,且u2、v2∈E(G2)或者u2=v2,且u1、v1∈E(G1)}.星图Sm表示完全偶图K1,m,Pn表示长为n的路.这里确定了星图S5及5个六阶图与路的笛卡儿积图的交叉数.