若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).     

若干图的广义字典积的点可区别边染色

在图G与不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积G[hn]中,若Hi≌H,i=0,1,…,n-1,则将G[hn]记为G[H],其中G[H]是G与H的字典积。图G的点可区别边染色所需最少的颜色数称为G的点可区别边色数,记为χ'vd(G)。对任一满足χ'vd(G)=Δ(G)的图G,给出了参数χ'vd(G[hn])的两个上界,并证明这些上界是可达到的,其中hn=(Hi)i∈{0,1,…,n-1}中的每一个Hi均为m阶简单图。另外证明了:如果χ'vd(G)=Δ(G),χ'vd(H)=Δ(H)且Δ(G[H])=Δ(H[G]),则χ'vd(G[H])=χ'vd(H[G]),其中G与H分别为n阶与m阶的简单图。     

单圈图的邻点可区别全染色

给出了圈的阶数至少为4的单圈图的邻点可区别全色数.如果E(G[VΔ])=,则χat(G)=Δ(G) 1,否则,χat(G)=Δ(G) 2,其中Δ(G)表示图G的最大度.     

完全二部图K_(3,n)(n≥18)的点可区别E-全染色

G是一个简单图,G的一个E-全染色f是指使相邻点着不同色且每条关联边与它的端点着以不同的色的全染色。设f为G的一个E-全染色。对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联的边的颜色所构成的集合。若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为是图G的点可区别的E-全染色,简称为VDET染色。图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数或简称为VDET色数,记为χevt(G)。讨论并给出了完全二部图K3,n(n≥18)的点可区别E-全色数。     

完全二部图K10,n(10≤n≤90)的点可区别E-全染色

图G的一个E-全染色f是指使相邻点染以不同颜色且每条关联边与它的端点染以不同颜色的全染色。对图G的一个E-全染色f,一旦∠u,v∈V(G), u≠v,就有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,则f称为图G的点可区别的E-全染色,简称为VDET染色。令χ^e_vt(G)=min{k|G存在k-VDET染色},称χ^e_vt(G)为图G的点可区别E-全色数。利用分析法和反证法,讨论并给出了完全二部图K_10,n(10≤n≤90)的点可区别E-全色数。     

完全二部图K_(3,n)(3≤n≤17)的点可区别E-全染色

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.     

关于Qn的可观测性

文献[3]中给出了当2≤n≤5时，n维立方图Qn的可观测性obs(Qn)的值．本文给出当6≤n≤11时，Qn的obs(Qn)的值，并提出一个关于obs(Qn)值的猜想。     

几类笛卡尔乘积图的邻点全和可区别全染色

设f:V(G)∪E(G)→[k]是图G的一个非正常的k-全染色,令权重 φ(x)=f(x)+∑x∈e f(e)+∑y∈N(x)f(y),其中,N(x)={y∈V(G)|xy∈E(G)}对任意的边uv∈E(G),如果有φ(u)≠φ(v)成立,则称f为图G的一个邻点全和可区别非正常k-全染色.图G的邻点全和可区别非正常全染...     

P_m∨S_n的点可区别全色数

设G是简单图,f 是从V(G)∪E(G) 到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(u)}∪{f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别全染色(简称为k-VDTC).数χv t(G)=min{k|G有k-VDTC}称为图G的点可区别全色数.给出m阶路Pm和n 1阶星Sn的联图的点可区别全色数.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

mK的点可区别全染色mK的点可区别全染色

 利用色集事先分配法, 借助于矩阵构造具体染色及递归法的方法, 研究图的点可区别全染色问题, 给出了m个K4的点不交的并mK4的点可区别全色数χvt(mK4)的确切值, 即“如果k-14<4m≤k4, m≥2, k≥6, 则χvt(mK4)=k”. 验证了VDTC猜想对mK4成立.     

P_m∨W_n的点可区别全色数

根据点可区别全染色的概念及其染色方法,讨论了路与轮联图的点可区别全染色,给出了路与轮联图的点可区别全色数的结论及其证明,为进一步探讨其他联图的点可区别全染色提供了理论证据,丰富了图的点可区别全染色的结果.     

项链的若干染色问题

 图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用。染色问题是近年来图论研究的热点,全染色,特别是邻点可区别全染色又是染色问题中的难点。本文研究了当h≥3 (h能确定项链的顶点个数,N_h中的h表示项链有2h+2个顶点)时,项链的邻点可区别全染色、点边邻点可区别全染色和关联邻点可区别全染色。通过在项链的点边集合与色集合之间构造一种一一对应关系,得到它们的色数分别是5、3、4,同时给出了具体的染色方案。     

关于几类特殊图的Mycielski图的点可区别全色数

讨论并得到了路、圈、完全图、星、扇、轮的Mycielski图的点可区别全色数.     

几类图的相邻顶点可区别的全染色

给出了几类特殊图相邻顶点可区别的全色数,如双路间和二部(V1,V2)间叠加匹配形成的系列图、双圈(prism)、双轮.并得到边连通度λ(G)=1的图相邻顶点可区别的全染色的性质.     

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk（G）（其中k为正整数）的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.     

点不交的m个C3]的并的点可区别全染色

利用μ(G)的定义确定了点不交的m个C₃(m≥2)的并的点可区别全色数的下界, 并借助矩阵给出了点不交的m个C₃(m≥2)的并的点可区别全染色方法, 进而确定了它的点可区别全色数.     

一类含有4-圈的单圈图一般点可区别全染色

设G为简单图.设f是图G的一个一般全染色,若对图G的任意两个不同的顶点u、v,有C(u)≠C(v),则称f为图G的一般点可区别全染色(简记为GVDTC).对图G进行一般点可区别全染色所需要的最少颜色数称为图G的一般点可区别全色数.将一类含有4-圈的单圈图悬挂边的染色按从小到大的顺序排列,探讨了它的一般点可区别全染色,确定了它具有一般点可区别全染色,并得到了它的一般点可区别全色数.     

m个点不交的C_4的并的点可区别全染色

给出了m(m≥2)个点不交的C4的并的点可区别全色数。     

几类有趣图的邻点可区别全染色

在正常全染色的定义下,使得任两相邻顶点的色集不同,这就是邻点可区别全染色.顶点v的色集是v的颜色其与及v关联的所有边的颜色.我们给出了几类有趣图的邻点可区别全色数.