共查询到20条相似文献,搜索用时 31 毫秒
1.
利用完全3部图K1,5,n的交叉数的结果,继续对联图Sm∨Cn(m=5)的交叉数进行研究,得到了cr(S5∨Cn)=Z(6,n)+4「n2」+3. 相似文献
2.
已经确定的五阶图与路Pn的联图的交叉数较少,作者继续深化这方面的研究,得到了联图K2,3 V Pn与{K2,3+e}V Pn的交叉数为Z(5,n)+n+1. 相似文献
3.
图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3. 相似文献
4.
确定图的交叉数是NP.完全问题.目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z(6,n)+2n+[n/2]. 相似文献
5.
李丽萍 《数学的实践与认识》2014,(11)
目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈. 相似文献
6.
用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4. 相似文献
7.
Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3. 相似文献
8.
在KlescM给出的完全图K_4∨P_n的交叉数的基础上,得到了cr(K_4∨C_n)=Z(4,n)+n+4,n≥3.特别地,当n=3时,cr(K_4∨C_3)=cr(K_7)=9,由此得到完全图K_7的交叉数另一种证明方法. 相似文献
9.
10.
11.
12.
13.
设k,n1和n2是3个正整数,G=(V1,V2;E)是一个二分图,使得|V1|=n1,|V2|=n2,其中n1≥2k+1,n2≥2k+1并且n1-n2≤1.如果对任意不相邻的x∈V1和y∈V2,都有d(x)+d(y)≥2k+2,则G包含k个相互独立的圈.以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题. 相似文献
14.
利用Kleitman D J给出的完全二部图的的交叉数cr(_(5,n))=Z(5,n)的结果,分别得到了联图G_(12)∨P_n,G_(15)∨P_n,G_(18)∨P_n的交叉数.同时,给出了目前已知的所有五阶图与路的联图交叉数情况. 相似文献
15.
K2,4×Sn的交叉数 总被引:1,自引:0,他引:1
Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图$K_{2,4}\times S_{n}$的交叉数是$Z(6,n)+4n.$ 当$m\geq 5,$猜想${\rm cr}(K_{2,m}\timesS_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor$. 相似文献
16.
如果n是正整数,我们用f(n)表示丢番图方程4/p=1/n_1+1/n_2+1/n_3的正整数解(n1,n2,n3)的个数.对于素数p,f(p)可以分解为f1(p)+f2(p),这里fi(p)(i=1,2)为分母n1,n2,n3中恰有i个能被p整除的解的个数.本文我们将研究关于均值∑p〈xfi(p),i=1,2,的估计,其中p表示素数. 相似文献
17.
18.
关于完全t部图K(n1,n2,…,nt)的色唯一性 总被引:1,自引:1,他引:0
设P(G,λ)是图G的色多项式,如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称G是色唯一图。这里通过比较图的特征子图的个数,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,1≤i,j≤t且min{n1,n2,…,nt}充分大,K(n1,n2,…,nt)是否为色唯一图?)。证明了,若|ni—nj|≤2且t↑∑↑i=1 ni〉t^2/2+t√t-1,则K(n1,n2,…,nt)是色唯一图;若αi=0或k,t↑∑↑i=1 n+αi〉t^2k^2/8+|tk|/2√t-1,则K(n+α1,n+α2,…,n+αt)是色唯一图。其条件比文献[4]中的条件较好一些。 相似文献
19.
设G=(V,E)是2(或3)-边连通的简单图,独立数为α,围长为g,n=|V|.若下列条件之一成立:(1)独立数α<3g2(或6g-21);(2)对G中任意含有m=3g2(或6g21)个顶点的独立集{v1,v2,...,vm}V,当g为偶数时,im=1dG(vi)n+4(或n-11);当g为奇数时,im=1dG(vi)n2(或n+1).则G是上可嵌入的. 相似文献