共查询到20条相似文献,搜索用时 31 毫秒
1.
图染色的基本问题是确定各种染色法的色数.图G和H的直积图G(×)H是一类很重要的图积,给出了直积图Cm(×)Pn的全染色的方法,得到其全色数Xn(CM(×)Pn)={4n=2 5n≥3,并进一步推广到图的正常全染色,得到其全色数Xn(G(×)Pn)-{△(G)+2n=2 2△(G)+1n≥3. 相似文献
2.
3.
图染色的基本问题是确定各种染色法的色数.图G和H的直积图G×H是一类很重要的图积,给出了直积图Cm×Pn的全染色的方法,得到其全色数x″(Cm×Pn)={4n=2 5n≥3,并进一步推广到图G×Pn的正常全染色,得到其全色数x″(G×Pn)={△(G)+2=2, 2△(G)+1n≥3. 相似文献
4.
5.
设Pm,Pn,ps(m,n,s≥3)分别为3条路,参照直积图的定义,定义了直积Pm(○)Pn(○)Ps,给出其全染色及邻强边染色的计算方法,得到其全色数xt(Pm(○)Pn(○)Ps)=9和邻强边色数x'as(Pm(○Pn(○)Ps)={9 m,n,s≥4,8其它,并进一步给出一个猜想:xt((○)n i=1Pi)=2... 相似文献
6.
设Pm,Pn,ps(m,n,s≥3)分别为3条路,参照直积图的定义,定义了直积Pm(○)Pn(○)Ps,给出其全染色及邻强边染色的计算方法,得到其全色数xt(Pm(○)Pn(○)Ps)=9和邻强边色数x'as(Pm(○Pn(○)Ps)={9 m,n,s≥4,8其它,并进一步给出一个猜想:xt((○)n i=1Pi)=2n+1=x'as((○)n i=1 Pi) 相似文献
7.
讨论笛卡儿积图P_2×P~n当n≡0(mod 4)时邻点可区别Ⅰ-均匀全染色问题,根据该类图的结构性质,通过构造法给出它们的邻点可区别Ⅰ-均匀全染色方法,从而有效地确定了其邻点可区别Ⅰ-均匀全色数为4. 相似文献
8.
9.
李大超 《海南师范大学学报(自然科学版)》2001,14(4):1-5
该文定义:一个简单图G=(V,E)是k-优美的(k≥1为整数),如果存在单射f:V(G)→{0,1,2,…,|E| k-1}使得对所有的边uv∈E(G),由f*(VV)一丫(V)-/(V门导出的映射 f*:E(G)→{k,k 1,…,|E| k-1}是双射。若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图。该文还证明了积图Pn×C2m、P2n×C2m 1、P2n×Cm的细分图是k-优美图。 相似文献
10.
Cm×Cn的邻点可区别全色数 总被引:2,自引:2,他引:0
给出了图Cm×Cn的一种全染色方法,并证明了该染色是邻点可区别的,从而得到了Cm×Cn的邻点可区别的全色数:xat(Cm×Cn)=6.此结果尚未见其他文献报道. 相似文献
11.
研究了图K_3~n和D_(n,4)的邻和可区别全染色.根据图K_3~n和D_(n,4)的结构特点,利用穷染的方法得到了图K_3~n和D_(n,4)的邻和可区别全色数. 相似文献
12.
图G的一个(p,1)全标号是与频道分配有关的一种染色,它是从V(G)UE(G)到一个整数集合的映射,且满足:1)图G的任意两个相邻的顶点得到不同的整数;2)图G的任意两个相邻的边得到不同的整数;3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差P.一个(p,1)一全标号的跨度是指最大标号数与最小标号数的差.图G的所有(P,1)-全标号函数中最小的跨度,称为图G的(p,1)-全标号数,记为λTP(G).本文我们证明了对任意的图G,其最大度△是偶的且至少是10,则λT2≤2△-1.另外对于任意的简单连通图G,其最大度为△,如果G的最大度点的邻点中至多有△-1个最大度点,则λTP(G)≤p+4. 相似文献
13.
14.
图K_n\E(F_3)(n=17,19)的点可区别全染色 总被引:1,自引:1,他引:0
一个图的全染色被称为点可区别的即对任意2个点的相关联元素及其本身所染颜色构成的集合不同.给出了图Kn\E(F3)(n=17,19)的一种点可区别全染色方法,利用此方法得出了图Kn\E(F3)(n=17,19)的点可区别全色数. 相似文献
15.
两个图G1和G2的笛卡尔积图G1×G2是这样一个图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2∈E(G2),或者u2=v2且u1v1∈E(G1)}.确定了笛卡尔积图K3,3×Pn的交叉数为7n-1. 相似文献
16.
设G是简单连通图,G的庀.正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色.这样的后中最小者称为G的邻点可区别全色数.本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数. 相似文献
17.
18.
设G1 和G2 是两个连通图,则G1 和G2 的Kronecker积G1 ×C2 定义如下:V(G1 ×G2)=V(G1)×V(G2),E(G1 ×G2)= {(u1,v1)(u2,v2):u1u2 ∈E(G1),v1v2 ∈E(G2)}.该文证明了如果G =G1 ×G2 是平面图并且Gi ≥3,那么G1 和G2 都是平面图;还完全确定了Pn ×G2 的平面性,n =3,4. 相似文献
19.
20.
《哈尔滨师范大学自然科学学报》2016,(1)
设G(V,E)是一个图,f为G的一个k-邻点可区别I全染色,若f满足||V_i∪E_i|-|V_j∪E_j||≤1(i≠j),其中,V_i∪E_i={v|f(v)=i}∪{e|f(e)=i},则称f为G的一个k-均匀邻点可区别I-全染色.给出风车图K_3~t,图D_(m,4)和齿轮图珟W的均匀邻点可区别I-全染色,同时,通过两边夹逼的方法得到了它们的均匀邻点可区别Ⅰ-全色数的确定值. 相似文献