共查询到10条相似文献,搜索用时 15 毫秒
1.
点可迁图的限制边连通度 总被引:8,自引:0,他引:8
设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论
设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3. 相似文献
2.
Hamiltonian图的泛圈性的一个充分条件 总被引:4,自引:0,他引:4
设G是一个n阶图,若对于每一个k(3≤k≤n),G都含有长度为k的圈,则称G为泛圈图. 在[1]中, R.J, Faudree等证明了如下结果: 定理A设G是一个n-阶2-连通图,δ(G)≥t.若对于G中任意两个不相邻的点u和v,均有 |N(u) ∪ N(v)|≥n-t,则 G是 Hamiltonian图. 根据 Bondy在[4]中的想法:几乎任何一个 Hamiltonian图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测:设图G满足定理A的条件,则G是泛圈圈或者 n=2t; G≌K_(t,t)… 相似文献
3.
4.
图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1). 相似文献
5.
设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的. 相似文献
6.
图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。 相似文献
7.
刘春峰 《纯粹数学与应用数学》1998,14(1):42-46
设G是一个简单图,L=u1u2…ut是G中的一个路,定义L的度d(L)=∑ti=1d(ui),其中d(ui)为ui在G中的度数.本文证明了:若G是n≥3阶几乎无桥的简单连通图,GK1,n-1,且对G中任何两个无公共点的二长路L1,L2,有d(L1)+d(L2)≥2n-1,则G有一个D-闭迹,从而G的线图L(G)是Hamilton图. 相似文献
8.
设f是区间I=[0,1]上的扩张的单峰函数,λ是f的扩张常数。又设K≥3是奇数,n≥3是整数,λk是方程x^k-2x^k-2-1=0的最大实根,μn是方程x^n-2x^n-1+1=0的最大实根,本文用较简单的方法证明了,当λ≥λK时,f中含有K-周期轨道,当λ≥μn时,f中含有相对于自身的RL^n-2C型单峰周期轨道。此外,本文还讨论了一类方程x^nη(x)=ζ(x)的根的极限度最性质。 相似文献
9.
区间上平顶单峰扩张自映射的周期轨道 总被引:2,自引:0,他引:2
设t(0<t<1)是一个常数,n≥3是奇数,m≥0及k≥1是整数,P0(x)=x-1,Pi(x)=(x2i-1-1)Pi-1(x)(i≥1),rmn(t)及rk(t)分别是方程Pm(x)(x2mn-2x2m(n-2)-1)-t(x2mn-1)(x2m+1)=0及Pk-1(x)-t(x2k-1+1)=0在(1,+∞)上的唯一实根,f是闭区间I=[0,1]上的峰顶区间长度为t的平顶单峰扩张自映射.本文证明了,若f的扩张常数λ≥rmn(t)(或>rk(t)),,则f有2mn(或2k)周期点.此外,本文还指出,当1<λ<rmn(t)(或≤rk(t)时,在I上存在着具有扩张常数λ及峰顶区间长度t却无2mn(或2k)周期点的平顶单峰扩张自映射 相似文献