共查询到20条相似文献,搜索用时 281 毫秒
1.
《牡丹江师范学院学报(自然科学版)》2016,(2)
通过分类讨论,归纳综合的方法,研究一个路与一个完全二部图直积的L(2,1)-标号问题,得到以下的结果:(1)当n≥3时,P_3×K_(n,n)的L(2,1)-标号数为3n;(2)当n≥3时,P_4×K_(n,n)的L(2,1)-标号数为3n;(3)当m≥5,n≥3时,P_m×K_n,n的L(2,1)-标号数为3n+1. 相似文献
2.
陈东灵 《山东科技大学学报(自然科学版)》1992,(1)
本文给出了若干完全图的联(nK_r+mK_s),圈、路和完全二部图分别与完全图的补图的字典式积(C_m(K_n)、L_m(K_n)和K_(a,b))以及完全r—部图(K_(n1,n2,…nr))等几类图的联结数。 相似文献
3.
n个顶点的完全图K_s,其边着色红或蓝,得K_n的二色图.当二色图既不包含蓝色团K_s,又不包含红色团K_y,则记作K_n(3,p).如果把K_n(3,p)成立的最大n值记为R(3,p),那未形如K_(n(3,p)(3,p)的一系列二色图与形为r(3,p)的一系列Ramsey数相关,已知R(3,p)=r(3,p)-1[1].本文讨论两个问题:(1)当p≤7时,给出二色图K_(R(3,p))(3,p)的递增性质,即K_(R(3,p))(3,p)可在K_(R(3,p-1))(3,p-1)上生成;(2)在二色图K_(22)(3,7)上生成K_(27)(3,8).从而知R(3,8)≥27,随知Ramsey数r(3,8)≥28. 相似文献
4.
黄国泰 《海南大学学报(自然科学版)》1985,(2)
设K_n为n阶完全图,以色α_1…α_t着K_n的边。又以E_i表示K_n中着色α_i的边集,G(E_i)表示以边集E_i生成的部分图。如果有一着色方案,使得每一G(E_i)不包含l_j阶完全子图K_(li)(1≤i≤t)则称K_n为可(K_l_1,…,K_l_t)——着色图。记R(l_1,…,l_t)=max{n 1:K_n为可(K_l_1,…,K_l_t)——着色图}并称R(l_1:…,l_t)为关于参数l_1,…,l_t的Ramsey数。 相似文献
5.
邹园 《南京师大学报(自然科学版)》1986,(3)
本文所讨论的图都是有限、无向简单图,记为G=(V,E),其中V、E分別表示图G的顶点集、边集。K_n表示n个顶点的完全图,K_(n,n)表示每部有n个顶点的完全两部图;Pn表示n个顶点的路;Cm表示m个顶点的圈,当m为奇(偶)数时,称Cm为奇(偶圈;CmUnK_2表示顶点数为m 2n的图,其中m个点组成圈Cm,余下2n个点组成nK_2(n个K_2的并图)。 相似文献
6.
《华东理工大学学报(自然科学版)》2017,(6)
n阶(n≥6)简单连通无向图G的谱半径记为ρ(G)。依G的谱半径从大到小进行了排序,得到如下结果:ρ(K_n)ρ(K_n-K_2)ρ(K_n-P_3)ρ(K_n-2K_2)ρ(K_n-K_(1,3))ρ(K_n-C_3)ρ(K_n-P_4)ρ(K_n-P_3∪K_2)。 相似文献
7.
《南京大学学报(自然科学版)》2017,(1)
图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ″(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度ρ_l″(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图K_n,ρ″K_n=[(n+1)/2];(2)对完全二部图K_n,n,ρ″K_n,n=[(n+2)/2];(3)对Halin图G,ρ_l″(G)≤[(△(G)+2)/2]. 相似文献
8.
LEE证明了超立方体图Q_n存在完备码当且仅当n=2~m-1(m≥2是自然数),当且仅当它是完全图K_(n+1)的正则覆盖.本文中,给出了这个结论的一个简单证明,并把这个结论推广到了初等交换群的凯莱图中.证明了初等交换p-群Z_p~n(这里p是奇素数)的凯莱图有完备码当且仅当n=(p~m-1)/2 (这里m是自然数且n≥2),当且仅当它是完全图K_(2n+1)的正则覆盖. 相似文献
9.
考虑完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色.利用组合分析法、反证法及构造染色的方法,给出一类特殊完全二部图的点可区别E-全染色.结果表明:当6≤n≤10时,K_(6,n)的点可区别E-全色数为5;当11≤n≤38时,K_(6,n)的点可区别E-全色数为6. 相似文献
10.
利用组合分析的方法先讨论了完全二部图K_(5,7)的点强可区别全染色,在此基础之上给出了两种具体的关于完全二部图K_(5,7)的点强可区别全染色方案.此结果的给出不仅确定了完全二部图K5,7的点强可区别全色数为9,而且对于胡志涛所提出的关于完全二部图的点强可区别全染色的猜想:"如果m≥4且n2 m-2时,那么χvst(Km,n)=n+3"中当m=5时作出了否定,从而进一步确定了此猜想成立的范围. 相似文献
11.
图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2]. 相似文献
12.
一个实用的检验Kn(3,p)的算法 总被引:2,自引:2,他引:0
设Kn是n个顶点的完全图,若对Kn的每条边着以红色或蓝色,并且图中既不包含红色团K3也不包含蓝色团Kp,这样就得到一个二色边图Kn,同时将这种染色所得的图记为Kn(3,p),把使Kn(3,p)成立的最大值记为R(3,p),R(3,p)=r(3,p)-1,r(3,p)是Ramsey数,本给出一个实用的算法,可以对给定连通图检验Kn(3,p)是否成立 。 相似文献
13.
顾成扬 《四川师范大学学报(自然科学版)》2004,27(6):607-609
如果Kn(t)能分解成一族同构于G的边不交的子图的集合,那么称Kn(t)存在G分解,讨论了当G是K3 e时,Kn(t)的G分解的存在性并给出其充要条件是:参数n,t满足下列条件之一:(1)t为偶数且n≥3;(2)t为奇数且n≡0,1(mod8)。 相似文献
14.
15.
设Kn,n表示每部分具有n个顶点的完全二部图,I为Kn,n的一因子.讨论了Kn,n-I的循环m-圈分解的存在性,并给出了Km+1,m+1-I存在循环m-圈分解的一个充分必要条件. 相似文献
16.
对于一个图G,一般情况下计算它的竞赛数k(G)是很困难的。本文给出了关于完全三部图Kn1,n2,n3(n1≥n2≥n3≥2)的边团覆盖数和竞赛数:θe(Kn1,n2,n3)=n1n2 k(Kn1,n2,n3)={n1n2-n1-n2-n3+4 n1≥n2=n3 n1n2-n1-n2-n3+3 n1≥n2〉n3 相似文献
17.
mi(1≤i≤r)为偶数且r∑(i=1)mi=2k(k≥1).Kn,n为偶图,I为Kn,n的一因子.证明了Kn,n+I可分解为(m1,m2,…,mr)-圈的充分必要条件为2k│n(n+1)且n为奇数.进一步,Kn,n+I可分解为循环的(m1,m2,…,mr)-圈充分必要条件为2k=n+1且n为奇数. 相似文献
18.
19.
林育青 《山西师范大学学报:自然科学版》2009,23(3):15-19
本文研究完全图、完全多部图的优美性,主要得到以下结论:完全图Kn是优美图的充要条件是该图的顶点数不超过4,完全多部图K1,m,n、K2,m,n都存在优美标号算法,从而说明它们都是优美图等. 相似文献