共查询到20条相似文献,搜索用时 0 毫秒
1.
一类完全r-部图的邻点可区别全染色 总被引:3,自引:0,他引:3
一个正常的全染色满足相邻点的点染色及关联边的色集不同时,称为邻强全染色,其所用最少染色数称为邻强全色数(或邻点可区别的全色数).给出了一类特殊的完全γ-部图邻点可区别的全色数. 相似文献
2.
A.C.Burris猜想:对于一个简单图G,它的邻点可区别的全色数aχt(G)≤Δ(G) 3其中Δ(G)表示G的最大度,本文证明了对Δ(G)=|V(G)|-1时,猜想为真. 相似文献
3.
简单连通图G(V,E)的κ-正常全染色f称为邻点可区别的,如果对G(V,E)的任意相邻两顶点,其顶点的颜色及关联边的颜色构成的集合不同.这样的κ中最小者称为G(V,E)的邻点可区别全色数.研究了路与双星图的联图PmV Sn,n邻点可区别的全染色问题,得到了联图PmV Sn,n邻点可区别的全色数. 相似文献
4.
王继顺 《兰州交通大学学报》2008,27(3)
对于阶数至少为2的简单连通图G(V,E)的一个κ-正常全染色.若f还满足对任意uv∈E(G),有C(u)≠C(v),其中C(u)={f(u)}U{f(uv)|uv∈E(G),v∈V(G)},那么称f为G的κ-邻点可区别的全染色(简记为κ-AVDTC),称min{κ| G有κ-邻点可区别的全染色}为G的邻点可区别的全色数,记作χaf(G).本文得到了联图CmVWn的全色数. 相似文献
5.
关于图邻点可区别上界的一点注 总被引:1,自引:1,他引:0
设G为一简单连通图.它的一个正常全染色叫做一个邻点可区别的全染色.如果满足:对G的任意两个顶点u,v,都有染点u以及与u相连的边所形成的色集与染点v以及与v相连的边所形成的色集不同.如果一个邻点可区别的全染色需要的色数为k,则把这个染色叫做k—邻点可区别的全染色(简记为k—AVDTC).对图G,记x′α(G)=min{k|G有一个k—AVDTC},称x′α(G)为图G的邻点可区别的全色数.本文给出了邻点可区别的全色数的一个上界. 相似文献
6.
G(V,E)是一个简单图,忌是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射.如果任意uv∈E(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称,是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.本文给出了扇与星、路、圈间的多重联图的邻点可区别E-全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}. 相似文献
7.
简单连通图G(V,E)的k-正常全染色,称为邻点可区别的,如果对G(V,E)的任意相邻两顶点,其顶点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为G(V,E)的邻点可区别全色数。研究了路与双星图的联图Pm∨Sn,n邻点可区别的全染色问题,得到了联图Pm∨Sn,n邻点可区别的全色数。 相似文献
8.
根据圈与圈(星、扇、轮)构造的冠图的结构性质,应用分析和构造函数法研究了邻点可区别V-全色数,得到了Gm·Gn,Gm,·Sn,Gm,·Fn和Cm·Wn的邻点可区别V-全色数,进一步验证了图的邻点可区别V-全染色猜想. 相似文献
9.
图的一个正常全染色满足相邻点的色集合互不包含时被称为Smarandachely邻点可区别全染色.使图G存在使用了k种色的Smarandachely邻点可区别全染色的最小数k称为图G的Smarandachely邻点可区别全色数,其中任意一点的色集合为该点所染色与其关联边所染色的并.文章给出了当(m相似文献
10.
将顶点集和边集分别为V(G)={vij|i=1,2,…,m;i=0,1,…,n-1},E(G)={v10 v20,v20 v30,…,vm0 v10}∪(m∪i=1{vij vik|j≠k;j,k=0,1,…,n-1})的图简记为Cm·Kn.给出了图Cm·Kn的邻点可区别全色数. 相似文献
11.
针对图的邻点可区别均匀 E-全染色问题,用结构分析的方法和穷举法研究了两类风车图的邻点可区别均匀 E-全染色问题,得到了它们的邻点可区别均匀 E-全染色数,并验证了结果的有效性。 相似文献
12.
围绕邻和可区别全染色猜想,研究了路与路、圈与圈的笛卡尔积图的邻和可区别全染色,应用构造染色函数法,确定了它们的邻和可区别全色数,证明了邻和可区别全染色猜想对于两类笛卡尔积图成立,给该猜想提供了更有力的证据. 相似文献
13.
C23n,C24n邻点可区别的全染色 总被引:5,自引:1,他引:4
设G(V,E)是阶数不小于2的简单连通图,n是自然数,V∪E到{1,2,…,k}的映射f满足Vuv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);А↓uv,uw∈E(G),(v≠w),f(uv)≠f(uw);А↓uv∈E(G),G(u)≠C(v).其中C(u)=f(u)∪{f(uv)|uv∈E(G)}.,f称为G(V,E)的一个邻点是可区分的全染色法,简记为k-AVDTC.其中最小的k称为G的邻点可区别的全色数。G^2是G再加上G中点间距离为2时连边后的图.本文得到了3n、4n阶圈C3n^2,C4n^2邻点可区别的全色数。 相似文献
14.
程辉 《兰州交通大学学报》2007,26(6):120-123
设G是简单图,k是正整数,f是V(G)∪E(G)到{1,2,…,k}的映射.对任意u∈V(G),记C(u)={f(u)}U{f(uv)|uv∈E(G),v∈V(G)}.如果f为G的正常全染色,且对任意uv∈E(G),有C(u)≠C(v).那么称f为G的k-邻点可区别全染色(简记为k-AVDTC).称xat(G)=min{k|图G存在k-AVDTC}为G的邻点可区别全色数.给出了联图Fs ∨ Km,n的邻点可区别全色数. 相似文献
15.
对简单图G(V,E),存在一个正整数k,使得映射f:V(G)∪E(G)→{1,2,…,k},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色,且称最小的数k为图G的点边邻点可区别全色数.本文讨论了星,扇,轮,圈等图的广义Mycielski图的点边邻点可区别全染色,得到了它们的点边邻点可区别全色数,其中每个点的色集合包含该点及其关联边的颜色. 相似文献
16.
对一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别全色数.本文得到了路Pm与星Sn的联图Pm∨Sn的邻点可区别全色数. 相似文献
17.
K11-uv的邻点可区别全色数 总被引:3,自引:2,他引:3
一个正常的全染色满足相邻点的点染色及关联边的色集不同时,称为邻强全染色,其所用最少染色数称为邻强全色数(或点可区别的全色数),证明了对u,υ∈V(K11),则xat(K11-uυ)=13。 相似文献
18.
对简单图G(V,E),若存在自然数k(1≤k≤△(G))和映射f:E(G)→{1,2,…,k}使得对任意相邻两点u,(υ)V(G),u(υ)E( G),当d(u)=d(υ)时,有C(u)=C(υ),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数. 相似文献
19.
对一个正常边染色满足相邻点的色集不同,称为邻点可区别的边染色,其所用最少染色数称为邻点可区别的边色数.定义图Sm*Sn为V(Sm*Sn)={w;u1,u2,…,um}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Sm*Sn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m;j=1,2,…,n}.本文得到了Sm*Sn的邻点可区别的边色数. 相似文献
20.
皇冠图Gn,m的邻点可区别边色数 总被引:3,自引:1,他引:3
定义皇冠图Gn,m为V(Gn,m)={ui|i=1,2,…,n}∪{vi|i=1,2,…,n|∪i=1 m|uij|j=1,2,…,m},E(Gn,m)={u1u2,u2u3,…u2u1}v1v2,v2v3,…vnv1}∪{u1vi|i=1,2,…,n}∪i=1^n{∪i=1^n{uijij|j=1,2,…,m}∪i=1^n{uijui(j 1|j 1,2,…|j=1,2,…,m-1}),(n≥3,m≥1)。本文得到了Gn,m的邻点可区别边色数。 相似文献