共查询到15条相似文献,搜索用时 46 毫秒
1.
一个有向图D的k-阶等周弧连通度定义为:γ+k (D)=min{|(U,U^-)|:U→∪V,|U|≥k,|U^-|≥k}.一个有向图满足γ^k+ (D)=β^k+ (D)时称为是γ^k+-最优的,其中β^k+ (D)=min{|(U,U)|:U→∪V,|U|=k,|U^-|≥k}.假设D是强连通d-正则的有向图且κ(D)≥3.本文我们证明了L(D)是γ2^+-最优的,其中L(D)表示D的线图. 相似文献
2.
3.
4.
子集SE(G)称为是图G的4-限制性边割,如果G-S不连通且每个连通分支至少有4个点.图G中基数最小的4-限制性边割称为4-限制性边连通度,记为λ4(G).本文确定了λ4(Qn)=4n-8.类似的,子集FV(G)称为图G的Rg-限制性点割,如果G-F不连通且每个连通分支的最小度不小于g.基数最小的Rg-限制性点割称为图G的Rg-限制性点连通度,记为κg(G).本文确定了κ1(L(Qn))=3n-4,κ2(L(Qn))=4n-8,其中L(Qn)是立方体的线图. 相似文献
5.
增广立方体AQn是超立方体Qn的一个变体,它不仅保留了超立方体Qn的几乎所有特征,还具有Qn不具有的一些嵌入特性.本文利用图结构分析的方法讨论了增广立方体AQn的2-额外点(或边)连通度,证明了κ2(AQn)=6n-18(n≥6),λ2(AQn)=6n-7(n≥5)。该结论对衡量互联网络的可靠性和容错性有借鉴意义。 相似文献
6.
广义笛卡尔积图的连通度 总被引:1,自引:0,他引:1
黄琼湘 《新疆大学学报(理工版)》1991,8(2):5-10
本文定义了图G_1、G_2的广义笛卡尔积图G=G_1∫G_2,并且证明了它们的连通度具有关系k(G)≥k(G_1)+k(G_2)。这一结果是对文[1]中关于G_1与G_2直积的结果的推广。此外,本文还讨论了G=G_1∫G_2的直径及Hamilton性。最后,利用G=G_1∫G_2的结果对循环图的连通度进行了讨论。 相似文献
7.
李学良 《新疆大学学报(理工版)》1988,(3)
[1]中给出了Euler环游图E_u(G)的定义,并证明了E_u(G)具有边-Hamilton性。[2]中证明了E_u(G)是正则图。本文得到如下结果,对|V(E_u(G)|≥2,E_u(G)的连通度恰好等于其正则度数。 相似文献
8.
对任一个n阶单图G,用a(G)表示G的代数连通度,Gc表示它的补图.着重证明了2个图类的代数连通度的N-G型的界:a(G)+a(Gc)≥1. 相似文献
9.
郭利涛 《浙江大学学报(理学版)》2018,45(4):391-393
Let G be a connected graph. The connectivity κ(G) of a connected graph G is the least positive integer k such that there is F⊂V,|F|=k, and G-F is disconnected or is a trivial graph. If every minimum vertex cut isolates a vertex of G, a graph G is super connected or super-κ. Define the inverse degree of a graph G with no isolated vertices as R(G)=1/(d(v)). In this paper, we show that let G be a connected graph with order n and minimum degree δ, if R(G)<1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)), then G is super-κ. 相似文献
10.
小度数点传递图的连通度 总被引:2,自引:1,他引:1
陈靓 《新疆大学学报(理工版)》2000,17(4):5-7
众所周知,k(k≤4)正则连通点传递图的连通度达到了它的正则度k,本文证明了除Cn◎K2(n≥4)外,每个5正则连通点传递图的连通度都是5,其中Cn◎K2是n长圈与完全图K2的字典积。 相似文献
11.
s-图的路由数源自于网格上行走的机器人的坐标规则问题.Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题:平面图上的路由数是否一定存在仅由半径为参数构成的界?本文引入有向s-图的路由数这一概念并证明该数等于其周长.这一结果表明无向s-图的路由数等于该图所有定向图的最小周长,同时也对上面的问题给出了一个反例.做为一个应用.我们证明乘积图的路由数等于其半径. 相似文献
12.
设G=(V,E)是一个连通图,S包含于E是一个边子集,如果G—S不再连通,且G—S的每一个连通分支都至少含有r个点,则称S为一个r-限制性边割.最小r-限制性边割中所含的边数为G的r-限制性边连通度,记作λ(G).如果对所有的i=1,…,r,λ(G)都达到其最大可能值,则称G为λ-最优图.王铭和李乔证明了:若G是一个d-正则的点传递图,d≥4,围长g≥5,或者G是一个d-正则的边传递图,d≥4,围长g≥4,则G是λ(g-1)-最优图.本文推广了这一结果,证明了:在同样的条件下,G是λg-最优图. 相似文献
13.
论证六角系统中是否存在同谱图,如果存在,找出这些同谱图,具有重要理论与应用价值,作者用不同于「1」的方法搜索出了同谱图。 相似文献
14.
左光纪 《新疆大学学报(理工版)》1989,6(1):13-16
B.Hedman在文[1]中介绍了构造线团图的一个算法.本文用这一算法得到了线团图的一些性质.它们涉及到图的连通度、直径和色数. 相似文献
15.
孟吉翔 《新疆大学学报(理工版)》2004,21(2):113-119
本文研究限制性边连通度的λ′-原子.运用所得结果可以证明Cayley图C(Sn,S)是最优超-λ的.这里Sn是n次对称群,S是若干由奇置换构成的共轭类的并,另外,我们还证明了C(Sn,S)是Vosperian的.除非它是完全二部图. 相似文献