首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 15 毫秒
1.
点可迁图的限制边连通度   总被引:8,自引:0,他引:8  
徐俊明 《数学年刊A辑》2000,21(5):605-608
设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.  相似文献   

2.
Hamiltonian图的泛圈性的一个充分条件   总被引:4,自引:0,他引:4  
徐军 《应用数学学报》2001,24(2):310-313
设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.
陈协彬 《数学研究》1999,32(2):146-150
设 n1 ≥ n 2 ≥ … ≥ nk ≥ 2 是整数. 若图 G 能边分解成 G1  G2  …  Gk , 这里 χ( Gi) = n i, i=1,2,…,k ,则称 G 有(n1 , n2 , …, nk )色因子 分解. 本文改进 了 Hakim i和 Schm eich el 关于图的色因 子分解的结果,作为推 论,推广了 M atula 和 Harary 等人的结果  相似文献   

4.
王铭  李乔 《数学年刊A辑》2003,24(3):315-320
图的超常边连通度是图的边连通度概念的推广.对于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.
设G是一个简单图,L=u1u2…ut是G中的一个路,定义L的度d(L)=∑ti=1d(ui),其中d(ui)为ui在G中的度数.本文证明了:若G是n≥3阶几乎无桥的简单连通图,GK1,n-1,且对G中任何两个无公共点的二长路L1,L2,有d(L1)+d(L2)≥2n-1,则G有一个D-闭迹,从而G的线图L(G)是Hamilton图.  相似文献   

8.
麦结华  曾凡平 《数学杂志》1994,14(3):369-374
设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  
孙太祥 《数学杂志》1996,16(3):312-320
设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)周期点的平顶单峰扩张自映射  相似文献   

10.
设G=Gn(i1,i2,…,ir)是连通循环图,且x(G)〈δ(G),本文得到了其连通度的明确表达式:x(G)=min(m/M(n/m,K)/:m是n的真因子,且/M(n/m,K)/〈n/m-1)。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号