首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
一类α-子图     
根据相关文献中给出的用以寻找欧拉生成子图极大边数的有效工具α-子图的概念,证明了对于任意G∈SL,Kl,m(l≥3,m≥3)是G的1-1/min{l,m}-子图.  相似文献   

2.
若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5  相似文献   

3.
若C有一个生成子图是欧拉图,则称G是超欧拉图(supereulerian graph).用SL表示全体超欧拉图的集合.1995年,赖虹建(LAI Hong-jian)、陈志宏(CHEN Zhi-hong)提出一个关于欧拉生成子图边数的公开问题;决定:L=min max G∈SL-{K1}{|E(H)|/|E(G)|} : H是G的欧拉生成子图}定义了一些含两棵边不相交生成树的图Fi(i=1,2,3),证明了如果G∈F3,那么L≥2/3.  相似文献   

4.
Catlin的 2 /3—猜想 :若G是超欧拉图 ,G≠K1 ,那么G有一个欧拉生成子图H ,使得|E(H) |≥ 23 |E(G) | .给出了Catlin的 2 /3—猜想的一些反例  相似文献   

5.
在相关文献中,引入了α-子图的概念来探索超欧拉图的极大欧拉生成子图的边数,并且证明了2-方体在加入一条新边的情况下是一个3/5-子图.研究了3-方体,证明了3-方体在加入一条新边的情况下是一个9/13 -子图.  相似文献   

6.
设k是一个正整数,G是一个顶点数为|G|=4k的图.若δ(G)≥2k+4,则图G有一个生成子图包含k-3个4-圈和2个6-圈,使得这k-1个圈是相互独立的.  相似文献   

7.
设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数.  相似文献   

8.
文献 [3 ]给出了判定超欧拉图的一个定理 :设G是一个 2 -边连通的不含K3-子图的简单图 ,n=|V(G) |≥ 3 1 如果δ(G) ≥ n1 0 ,并且G不能被收缩成K2 ,3,则G有一个欧拉生成子图 证明了在上述条件下 ,G有一个欧拉生成子图H使得 |E(H) |≥ 23 |E(G) | ,或者G -E(H)有平凡分支  相似文献   

9.
在相关文献中,引入了α-子图的概念来探索超欧拉图的极大欧拉生成子图的边数,并且证明了2-方体在加入一条新边的情况下是一个3/5-子图.研究了3-方体,证明了3-方体在加入一条新边的情况下是一个9/13-子图.  相似文献   

10.
得到了超欧拉图的一个特征性质:G是简单图,则G是超欧拉图当且仅当G中有边不交路P1,…,Ps,使得E(Pi)连通.利用它可以证明:当m,n不其端点两两不同,并且满足O(G)={Pi的端点|=1,2,…,s},G-∪si=1同时为3时,m×n型矩形网格图是超欧拉图.  相似文献   

11.
Catlin的2/3-猜想:若G是超欧拉图,G≠K1,那么G有一个欧拉生成子图H,使得|E(H)|≥2/3|E(G)|。给出了Catlin的2/3-猜想的一些反例。  相似文献   

12.
对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界.  相似文献   

13.
关于Catlin的2/3—猜想   总被引:6,自引:3,他引:3  
表示一个图,若G有一个欧拉生成图,则称G是超欧拉图。Catlin的2/3-猜想:设G是超欧拉图,G≠K1,则G存在一个欧拉生成子图H,使得E(H)/E(G)≥2/3。笔者证明了对于Cayley图,猜想成立。  相似文献   

14.
设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。  相似文献   

15.
本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m 1)/2],[(n 1)/2]}。  相似文献   

16.
证明了如下结果:(1)一个2-连通图G的Θ-图是2(ρ-1)连通的;(2)如果一个2-连通图G有两个单圈支撑子图,且这两个单圈支撑子图分别含m和n个悬挂点(m相似文献   

17.
证明了如下结果:(1) 一个2-连通图的⊙-图是2(p-1)连通的; (2)如果一个2-连通图G有两个单圈支撑子图, 且这两个单圈支撑子图分别含m和n个悬挂点(m相似文献   

18.
利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .  相似文献   

19.
文献[3]给出了判定超欧拉图的一个定理:设G是一个2-边值通的不含K3-子图的简单图,n=|V(G)|≥31。如果δ(G)≥n/10,并且G不能被收缩成K2,3则G有一个欧拉生成子图。证明了在上述条件下,G有一个欧拉生成子图H使得|E(H)|≥2/3|(E(G)|,或者G-E(H)有平凡分支。  相似文献   

20.
通过对图的奇顶点的导出子图做研究,得到了由奇顶点的导出子图的性质判定图的超欧拉性的方法,即当图的奇顶点的导出子图满足一定性质时,可得出图的超欧拉性.  相似文献   

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

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