共查询到20条相似文献,搜索用时 0 毫秒
1.
确定图的交叉数是NP-complete问题,现有的关于联图的交叉数的结果比较少,为此,讨论了五阶图4G分别与nK1,Pn及Cn的联图的交叉数. 相似文献
2.
摘要:目前已经确定的两个图的联图的交叉数结果比较少,为此讨论了五阶图G18分别与nK1,Pn的联图的交叉数,得到了cr(G18+nK1)=Z(5,n)+n+[n/2],n≥i;cr(G18+Pn)=Z(5,n)+n+[n+2,n≥2.其中nK1是n个孤立点构成的图,只是Pn个点的路. 相似文献
3.
探讨一个六阶图与路的联图的交叉数.利用完全二部图k6,n的交叉数结果,证明了该六阶图与路的联图的交叉数为:Z(6,n)+n+1,n≥2. 相似文献
4.
两个图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)}.图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全胛一问题.本文确定了若干树Tn(n≤4)与圈Cm的笛卡尔积图的交叉数. 相似文献
5.
两个图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).图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全NP-问题.本文确定了若干树Tn(n≤4)与圈Cm的笛卡尔积图的交叉数. 相似文献
6.
贺佩玲 《衡阳师范学院学报》2008,29(6)
用km,n表示完全二部图,用k4,m\e1,e2表示完全二部图k4,n去掉两条边e1、e2.本文确定了K4,n\e1,e2的交叉数为州z(4,n)-2[n/2]+2.K4,n\e1,e2. 相似文献
7.
Gyárfás在完美图概念的基础上,提出了色界函数的概念,并给出猜想:对于给定的森林F,存在整数函数f (F, x)使得每一个以F为禁用子图的图G都满足χ(G)≤f (F,ω(G)),其中χ(G)和ω(G)分别表示图G的色数和团数。通过分析禁用子图为P3∪P2的图结构,给出色界函数f (P3∪P2,ω(G))的一个上界;并且以此为基础,得到禁用子图为P3∪mP2的图色数上界。 相似文献
8.
9.
研究了联图CnVKn=2n的全色数,证明了当n〉5时,金色数XT(CnVKn)=2n,从而证明了CnVKn.满足全着色猜想. 相似文献
10.
董会英 《泉州师范学院学报》2013,31(2):1-7
图G的pebbling数f(G)是指在一个图G的顶点上以任意方式放置若干个pebble数目的最小值,满足通过一系列的pebbling移动使得任一指定目标顶点能得到一个pebble,而pebbling移动是从一个顶点处移走两个pebble并把其中的一个移到与其相邻的一个顶点上.文章定义了将两个图的直径端点之一粘接生成的一类粘接图,主要计算了一些粘接图的pebbling数,发现了两类满足pebbling数直径下界的图. 相似文献
11.
研究了联图Cn∨Kn=2n的全色数,证明了当n≥5时,全色数χT(Cn∨Kn)=2n,从而证明了Cn∨Kn满足全着色猜想. 相似文献
12.
对简单图G(V,E),f是从V(G)u E(G)到{1,2,…, k}的映射,K是自然数,若,满足(1) uv∈E(G),u≠v,f(u)≠f(v);(2) uv,uw∈E(G),v≠w,f(uv)≠f(uw);则称/是G的第一类弱全染色.给出了若干联图的第一类弱全色数. 相似文献
13.
14.
图划分具有广泛的应用,主要应用于VLSI(大规模集成电路)设计,并行计算,数据挖掘和图像分割等领域,因此得到了国内外学者的普遍关注和大量研究。由于图划分是NP-完全问题,因此本文在一般图划分问题基础上提出了特殊点割集及点分割数的概念,主要应用图的连通性原理分析,给出路、圈、扇图、轮图及完全二部图及联图P n,C n,F1n,W n,K m,n,m i=1ΣK n i等的点分割数,并分析讨论了完全图Kn删除一个独立边集后,其点分割数的变化情况。 相似文献
15.
林启法 《宁德师专学报(自然科学版)》2010,22(3):233-234,242
Hamilton图是图论中重要的一类特殊图.主要证明了两个图的联图是Hamilton图,从而进一步证明了n个图的联图也是Hamilton图. 相似文献
16.
17.
《绵阳师范学院学报》2015,(11):15-17
由文献[1]可知,标号图的发展比较快,但树和2-正则图[2]的联的Cordial性仍未解决.本文以分类讨论的思想和方法解决了这一问题,为完善和发展Cordial图的内容做出了一份贡献.同时应用本文结论也很容易证明D(1,2)图[3]是Cordial图的结论. 相似文献
18.
19.
刘沈荣 《绵阳师范学院学报》2009,28(11):22-24
图G=(V,E)的首先适应着色数是在贪婪着色中最坏情形所需要的颜色数,记为xFF(G)。也称之为Grundy数,其等价定义为:V的有序拆分V1,V2,…,Vk的最大分类数为k,其中Vi为独立集且对每个1≤i〈j≤k及x∈Vj存在-y∈Vi使得x和y相连。文章证明了在稀疏随机图中,可以很高的概率满足(1-ε)n/logbnp≤xFF(G(n,P))≤(1+ε)n/logbnp。其中事件A以很高的概率成立是指对于任意当n→∞时,P(A发生)→1。 相似文献
20.
把星Sm中的每一个点与扇Fn中的每一个点相连,得到星与扇的联图,记为SmVFn.本文给出了SmVFn的邻点可区别全色数. 相似文献