共查询到20条相似文献,搜索用时 9 毫秒
1.
一类笛卡尔积图的交叉数 总被引:1,自引:0,他引:1
图的交叉数是拓扑图论中的一个重要研究课题,因为其难度,能够确定交叉数的图类很少.运用同胚法和数学归纳法,确定了一类六阶图与路的笛卡尔积交叉数. 相似文献
2.
确定一个图的交叉数是NP-完全问题。结合图的交叉数来刻画图的特征,目前相关结果非常少,针对连通的因子图而言,交叉数为1的联图G_1∨G_2的充要条件已经被刻画。在文中,我们试图将结果推广,也考虑不连通的因子图,刻画了当v(G_1)=3且cr(G_1∨G_2)=2时因子图G_1和G_1需满足的充要条件。 相似文献
3.
计算了一个具体图类Hn的交叉数,然后研究了一个五点图G和Pn路的联图G∨Pn,并用归纳假设法证明了这个五点图和路的联图的交叉数Cr(G∨Pn),即当n≥2时,Cr(G∨Pn)=4 2n n 2-1+n2+1. 相似文献
4.
李敏 《河南师范大学学报(自然科学版)》2013,41(4):40-44
详细的讨论了和两个5阶图Gi(i=11,14)有关的联图的交叉数,分别是:Gi+Hn,Gi+Pn和Gi+Cn,其中Hn是由n个孤立点构成的图,Pn和Cn分别是含n个点的路和圈. 相似文献
5.
6.
交叉数是拓朴图论研究中的一个重要课题,在笛卡尔积结论的基础上证明了一类7阶图与路的笛卡尔积图的交叉数. 相似文献
7.
阶数不大于5的有关的联图的交叉数已经有了一些确切结论,文中更进一步研究六阶图与路的联图的交叉数,并确定了S5∨Pn 以及其他5个六阶图 G∨Pn的交叉数. 相似文献
8.
《邵阳学院学报(自然科学版)》2017,(4)
图的交叉数是表征一个图的非平面性的一个重要的参数,是拓扑图论中的前沿难题,求解图的交叉数是NP-hard问题。本文确定了一个特殊6阶图H与n个孤立点nK_1的联图的交叉数是Z(6,n)+n。 相似文献
9.
晏惠琴 《青海师范大学学报(自然科学版)》2008,(3):9-11
令k,m是确定的整数.本文研究几个顶点的一类图G(H,k,H’,m)的Fibonacci数,并给出了这类图的Merrifield—Simmons指标及其序列. 相似文献
10.
给出了两个圈的联图、完备图与完备二部图的联图以及若干完备图的并与若干完备二部图的并之联图等几类联图的联结数的计算公式。 相似文献
11.
《山西师范大学学报:自然科学版》2017,(3)
目前已确定交叉数的六阶图与路,圈的联图较少.在Kleitman给出的完全二部图的交叉数cr(K6,n)=Z(6,n)的结果的基础上,通过分析法得到了一个特殊六阶图H与路Pn,与圈Cn的联图交叉数分别为Z(6,n)+n+■n/2」+1和Z(6,n)+n+■n/2」+3. 相似文献
12.
联图G∨H表示将G中每个点与H中的每个点连边得到的图.在Klesc M给出所有3阶图和4阶图与圈Cn联图的交叉数的基础上,利用反证法和排除法确定了G1,G2,G3三个5-阶图与圈Cn联图的交叉数,他们的交叉数分别是cr(G1∨C2)=Z(5,n)+2[n/2]+2,cr(G2∨Cn)=Z(5,n)+2[n/2]+2,cr(G3∨Cn)=Z(5,n)+2[n/2]+3. 相似文献
13.
《扬州大学学报(自然科学版)》2015,(1)
分别讨论了5阶图G16与nK1,Pn,Cn联图的交叉数,得到cr(G16+nK1)=Z(5,n)+n+n/2,n≥1;cr(G16+Pn)=Z(5,n)+n+n/2+1,n≥2;cr(G16+Cn)=Z(5,n)+n+n/2+3,n≥3,其中nK1是n个孤立点构成的图,Pn,Cn分别是含n个点的路和圈. 相似文献
14.
竞争数和进化数是竞争图和进化图的重要研究内容,研究一类图的竞争数和进化数的结果表明,每个这类图都含有且仅含有一个阶数大于等于3的团。此结论推广了Kim,Roberts和Sheng的一些结果。 相似文献
15.
本文研究了路、圈、完全图相互间经过联运算以后所得图的边联结数,得到了Lm(?)Ln,Cm(?)Cn,Lm(?)Cn,Lm(?)Kn和Cm(?)Kn的边联结数的计算公式,这里Lx,Cx,Kx分别表示有x个点的路、圈、完全图。 相似文献
16.
确定一个图的交叉数是NP-完全问题,能够确定的图类很少,难度很大,是国内外图论学者普遍关注的热点问题.在本文中,作者主要考虑一个特殊的五点图和路与圈的联图的交叉数,并确定了{C5+e}∨Pn及{C5+e}∨Cn的交叉数. 相似文献
17.
在这篇文章中,引进了计算图交叉数的新的方法,利用辅助图计算了图C(n,m)的f-交叉数βf(n,m)),作为推论,导出了图C(n,3)和C(2m,m)的新的上界。 相似文献
19.
20.
考虑环柄对循环图交叉数的影响,并且给出了循环图交叉数的上界.特别地,循环图C(2m,m)和C(2m+l,m)的交叉数都等于1. 相似文献