共查询到19条相似文献,搜索用时 328 毫秒
1.
龚和林 《上海师范大学学报(自然科学版)》2005,34(2):33-36
设G的色多项式为P(G,λ)=λ^ko(λ-1)^k1…(λ—m 1)^km-1(λ-m)…(λ—n 1),其中,m≤n,且ki=1或2(i=0,1,…,m-1),且k0≤k1≤…≤km-1.本文给出了几类由上述形式色多项式决定的广义树,并证明了{{Kn,Km},{Kr}}是一个完全类当且仅当r=m-1或m. 相似文献
2.
设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图。令K(m,n,r)表示完全三部图,证明了(1)设m≤n≤r,0≤r-m≤4,若m≥2,则除去K(2,2,6)、K(2,3,6)、K(3,3,7)、K(3,4,7)外,K(m,n,r)是色唯一图。(2)若n≥4,0≤k≤2,则K(n-k,n,n k)是色唯一图。 相似文献
3.
文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。 相似文献
4.
李凤琴 《内蒙古大学学报(自然科学版)》2007,38(2):121-126
设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3≤m≤n≤r时,令s=1/√6√(n-m)2 (r-n)2 (r-m)2 12,若m n r>2√3s 3s2,则K(m,n,r)-A(|A|=2)是色唯一图;2)当m≥4时,K(m,m,m)-A,K(m,m,m 1)-A,K(m,m 1,m 1)-A,(|A|=2)都是色唯一图;3)设n,k为非负整数,则当n>k2 2√k2 6 k 2时,K(n-k,n,n)-A;当n>k2 2√k2 6-k/3 2时,K(n,n,n k)-A;当n>2√3k2 6 k2 2时,K(n-k,n,n k)-A(|A|=2)均为色唯一图. 相似文献
5.
邹辉文 《同济大学学报(自然科学版)》2002,30(8):1014-1018
设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图,用K(m,n)-A表示从K(m,n)中删去边子集A所得的二部图,令L2^-s(m,n)={K(m,n)-A||A|=s},研究一般形式的K(m,n)-A的色唯一性问题,通过引进色正规图类的概念,使用比较两个色等价图的色划分数的方法,得出G∈L2^-s(m,n)的色等价图仍然是属于L2^-s(m,n)的一般形式数值条件,进一步得出G∈L2^-s(m,n)(2≤s≤4)为色唯一图的一般形式数值条件,所得结果完全覆盖并推广了1997年以前该研究方向的相关结果。 相似文献
6.
林育青 《山西师范大学学报:自然科学版》2006,(2)
本文研究了图Pnk和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及Pn2仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论. 相似文献
7.
林育青 《山西师范大学学报:自然科学版》2006,20(2):6-9
本文研究了图Pkn和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及P2n仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论. 相似文献
8.
用P(G,λ)表示简单图G的色多项式,文章采用数学归纳法刻画了一类具有整根色多项式图的结构特征为P(G,λ)=λ(λ-1)(λ-2)m(λ-3)…(λ-n+1)(n≥3,n,m∈Z+),从而证明色等价类[G]中的图都是弦图. 相似文献
9.
设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G~H表示.令[G]={H\H~G).若[G]={G),称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2≤n1≤n2≤n3≤n4,得到了[G]С{K(x,y,z,w)-S|z y w =n1 n2 n3 n4,1≤z≤y≤z≤w≤n4-1,或1≤x≤y≤z≤n3-1和w=n4U{G},其中S是K(x,y,z,w)的某s条边组成的集合且K(x,y,z,w)-s表示从K(x,y,z,w)中删去S中所有边得到的图.从而证明了当n≥k 2,t≥2时,K(n-k,n,n,n)是色唯一的. 相似文献
10.
殷建 《山东大学学报(理学版)》2004,39(4)
研究稠密图T(1,2,n)∪(∪iCui)的色性,并刻画它的色等价图.其中,T(l1,l2,l3)(l1≤ l2≤l3)表示只有一个3度点,三个1度点,且唯一3度点到三个1度点的距离分别为l1,l2,l3的树,P(G,λ)和h(G,x)分别表示图G的色多项式和伴随多项式. 相似文献
11.
完全三部图K(m,n,r)的色唯一性的进一步结果 总被引:1,自引:1,他引:0
设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ),都有H与G 同构,则称G是色唯一图,令K(m,n,r)表示完全三部图。 相似文献
12.
13.
一类距离图的分数色数 总被引:1,自引:0,他引:1
摘要:主要讨论了距离图G(Z,Dm,k,k+1,k+2,k+3)(其中Dm,k,k+1,k+2,k+3={1,2,…,m}-{k,k+1,k+2,k+3})的分数色数,以及当2k≤m≤2k+5时G(Z,Dm,k,k+1,k+2,k+3)的色数。 相似文献
14.
严谦泰 《科技导报(北京)》2010,28(21):78-81
邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G(V,E)为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中,Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},记C(i)=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat(G)=min{k|G存在k-均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。 相似文献
15.
16.
图的点可区别无圈边色数的一个上界(英文) 总被引:2,自引:0,他引:2
图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度. 相似文献
17.
证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图. 相似文献
18.
利用差值转移的方法证明了,如果g(G)≥4则有X′a≤Δ(G)+4.图G=(V,E)是简单图,映射C:E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林. 相似文献