共查询到20条相似文献,搜索用时 62 毫秒
1.
李登信 《重庆工商大学学报(自然科学版)》2002,19(1):1-2
Catlin的 2 /3—猜想 :若G是超欧拉图 ,G≠K1 ,那么G有一个欧拉生成子图H ,使得|E(H) |≥ 23 |E(G) | .给出了Catlin的 2 /3—猜想的一些反例 相似文献
2.
李登信 《渝州大学学报(自然科学版)》2002,19(1):1-2
Catlin的2/3-猜想:若G是超欧拉图,G≠K1,那么G有一个欧拉生成子图H,使得|E(H)|≥2/3|E(G)|。给出了Catlin的2/3-猜想的一些反例。 相似文献
3.
李登信 《重庆工商大学学报(自然科学版)》2000,(3)
G表示一个图 ,若G有一个欧拉生成子图 ,则称G是超欧拉图。Catlin的 2 3—猜想 :设G是超欧拉图 ,G ≠K1,则G存在一个欧拉生成子图H ,使得|E(H) | |E(G) |≥ 2 3。笔者证明了对于Cayley图 ,猜想成立。 相似文献
4.
关于判定超欧拉图的收缩法 总被引:3,自引:0,他引:3
P.A.Catlin提出一个问题:设H是图G的一个连通子图,如果G关于H的收缩图G/H有一个欧拉生成子图,那么在什么条件下G也有一个欧拉生成子图?研究了这一问题,讨论了Catlin提出的用收缩法判定超欧拉图的两个定理,给出了一些实用的超欧拉图的判别方法。 相似文献
5.
综述了超欧拉图的生成子图边数问题,包括该问题的提出及研究发展过程,并罗列了两类公开问题:能否证明边数问题的下确界是35,若不能证明,能否找到更小的下确界?对一些著名的超欧拉图类,如具有两棵边不交的生成树的图等,能否证明其满足Catlin-猜想或35-猜想? 相似文献
6.
李登信 《重庆工商大学学报(自然科学版)》2008,25(3):223-225
若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. 相似文献
7.
关于Catlin的2/3—猜想 总被引:6,自引:3,他引:3
李登信 《渝州大学学报(自然科学版)》2000,17(3):1-4,39
表示一个图,若G有一个欧拉生成图,则称G是超欧拉图。Catlin的2/3-猜想:设G是超欧拉图,G≠K1,则G存在一个欧拉生成子图H,使得E(H)/E(G)≥2/3。笔者证明了对于Cayley图,猜想成立。 相似文献
8.
李登信 《重庆工商大学学报(自然科学版)》2007,24(3):215-217
设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数. 相似文献
9.
文献 [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)有平凡分支 相似文献
10.
李登信 《重庆工商大学学报(自然科学版)》2005,22(1):1-3
若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5 相似文献
11.
王斌 《西南师范大学学报(自然科学版)》2009,34(1)
图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e.给出了边-超欧拉图的一个度数和条件,即:设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d(u)+d(v)≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G(G关于e的剖分图)可以被收缩成K2.3或K2.5. 相似文献
12.
设G是一简单无向图,C(G)表示G的无向关联矩阵,Q(G)=C(G)C(G)^T,det(λI-Q(G)称为图G的拟拉普拉斯特征多项式,该文图的拟拉普拉斯特征多项式的系数进行了研究,给出了图的拟拉普拉斯特征多项式系数的一些性质,得到了正则图的线图,细分图,全图的的拟拉普拉斯特征多项式。 相似文献
13.
3连通图生成树上的可去边 总被引:1,自引:0,他引:1
摘要:设G是3连通图,e是G中的一条边.若G—e是3连通图的一个剖分.则称e是3连通图G的可去边.否则,称e是G的不可去边.本文给出某些3连通图的生成树上可去边的分布情况及数目。 相似文献
14.
完全二分图的生成树的个数 总被引:3,自引:0,他引:3
给出了生成子图的定义.证明了生成子图的构造定理和计数定理.提出了任意G(p,q)的生成树的计数方法和构造方法.介绍了完全二分图K3,3的生成树的计数和构造. 相似文献
15.
设G是含有n个顶点和ε条边的图,G的Zeta函数可以表示为ZG(u)=(1-u2)n-ε/f(u),其中f(u)=det(I-uA (G)+u2(D (G)-I)),A(G)与D (G)分别表示G的邻接矩阵与度对角矩阵。分别利用正则图的TU子图的权重ω和二部图的顶点n和边数ε来表示相应的f′(-1)的值。 相似文献
16.
17.
邓依群 《郑州大学学报(理学版)》2003,35(3):20-22
对两个给定的图G和H,以G H表示G和H的联,以G[H]表示G对图H的结合图,证明了如下结果:(1)G H是Menger图当且仅当G和H均为Menger图;(2)若G和H均为Menger图,且G的任一导出子图也是Menger图,则G[H]必为Menger图。 相似文献
18.
19.
20.
鲁富荣 《太原师范学院学报(自然科学版)》2012,(4):10-11
设k是一个正整数,G是一个顶点数为|G|=4k的图.若δ(G)≥2k+4,则图G有一个生成子图包含k-3个4-圈和2个6-圈,使得这k-1个圈是相互独立的. 相似文献