共查询到20条相似文献,搜索用时 62 毫秒
1.
根据n维超立方体Hn及其p次幂Hpn的结构特性,结合其顶点间距离与海明距离关系来确定其顶点坐标的性质,采用"脊"的技术和顶点着色的方法,对维数不超过7的超立方体三次幂的可区别数进行了研究.通过适当地选取顶点得到了H33的可区别数为8,H34的可区别数为5,H36和H37的可区别数都为2,及H35可区别数的一个上界为3. 相似文献
2.
超立方体的边可区别数 总被引:3,自引:1,他引:3
针对图(点)可区别数,提出了图的边可区别数,给出了n阶路Pn和n阶圈Cn的边可区别数;根据n维超立方体Hn及其p次幂Hpn的结构特性,对n维超立方体Hn和n维超立方体p(>2)次幂Hpn的边可区别数进行了研究,得到了n维超立方体及其高次幂Hpn的边可区别数的一个上界.即,当n=2时,H2的边可区别数为3;当n≥3时,Hn的边可区别数为2;当n≥4,n≥p>2时,Hpn的边可区别数小于等于3. 相似文献
3.
作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在长度为l的xy路除非当d=1时l=2,4. 相似文献
4.
李凤高 《湖南理工学院学报:自然科学版》2002,15(2):1-4
设IFq是具有q个元素的有限域,其中q是一个素数的幂.由IFq上n维仿射空间AG(n,IFq)的m面诱导的图r被研究.特别,r中任两个顶点间的距离通过它们的联的维数被确定,而r中任一个顶点的邻域也以显式给出. 相似文献
5.
谭学功 《暨南大学学报(自然科学与医学版)》2010,31(3)
为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1. 相似文献
6.
《中国科学技术大学学报》2015,(6)
考虑包含故障边的n(n≥3)维变形超立方体VQn,证明了:如果故障边数不超过n-2,那么VQn包含非故障边的Hamilton圈;如果故障边数不超过n-3,那么对任何两个不同顶点x和y,VQn包含非故障边的xy-Hamilton路.该证明方法采用归纳法. 相似文献
7.
董秀芳 《海南大学学报(自然科学版)》2014,32(3):200-204
以一个简单图G为基础,连接G的任意最短路长为k的2个顶点就可得到基础图G的k-幂图,研究了路的k-幂图和圈的2-幂图的邻点可区别E-全染色问题,并结合该类幂图的结构性质,运用构造法、反证法和穷举分类染色技术给出了其邻点可区别E-全色数,为确定图的各类染色问题提供了有效的借鉴. 相似文献
8.
确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)). 相似文献
9.
交叉立方体互连网络的Hamilton连通性 总被引:6,自引:2,他引:4
交叉立方体互连网络是超立方体的一个变型,它有一些比超立方体更好的性质.本文证明了n维交叉立方体CQn的又一个超立方体所不具备的性质,即当n≥1,n≠2时,CQn是Hamilton连通的,并给出了当n≥4时CQn中任意两个顶点间Hamilton路条数的一个下界4(2n-1-2)∏n-2i=3(2i-2)2. 相似文献
10.
研究图~$G$\,的星边色数~$\chi_{s}^{\prime}(G)$\,与其顶点数~$\nu$ 和边数~$\varepsilon$\,之间的关系. 证明了当~$\Delta(G)\geqslant2$\,时, 有~$\lceil\frac{8\varepsilon}{3\nu}\rceil\leqslant\chi_{s}^{\prime}(G)$. 得到了~$2$-维网格的星边色数, 并且给出了超立方体和~$d$-维网格的星边色数的可达上界和下界. 相似文献
11.
12.
13.
14.
设λKv是λ重ν点完全图,G是无孤立点的有限简单图。将G-设计(G-填充)记作(ν,G,λ)-GD((ν,G,λ)-PD)是指一个序偶(X,B),其中X是完全图Kν的顶点集,B是Kν中间构于G的子图(区组)的集合,使得Kν中每条边恰好(至多)出现在B的λ个区组中。讨论了3类7点7边图Gi(i=1,2,3)的图设计及最优填充问题,并给出了(ν,Gi,1)-GD及(ν,Gi,1)-OPD(i=1,2,3)存在的谱。 相似文献
15.
16.
17.
温一慧 《兰州大学学报(自然科学版)》2005,41(5):131-133
给出了弱边优美图的概念,指出了它的客观存在性及其与边优美图、非边优美图的关系.作为应用,讨论了完全偶图K1,n中的这三类图的存在问题. 相似文献
18.
路在平 《北京大学学报(自然科学版)》2003,39(1):1-5
设G是有限群,S是G的一个子集(可能含有单位元)。群G关于S的双Cayley图BCay(G,S)是以Gx{0,1}为点集而以{{(g,0),(sg,1)}|g∈G,s∈S}为边集的二部图。考查了双Cayley图BCay(G,S)的自同构群A,并决定了NA(Rι^r(G))的结构。 相似文献
19.
20.
董进全 《内蒙古大学学报(自然科学版)》1992,23(4):465-467
图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界. 相似文献