一类型超欧拉有向图

如果一个有向图D包含一个生成欧拉子有向图,那么称D是超欧拉图.Alsatami等人定义了两个有向图的2-和,并且给了两个有向图的2-和是超欧拉图的充分条件.论文将2-和的概念推广到了l-路和,同时给出了一些两个有向图的l-路和是超欧拉图的充分条件.     

广义棱柱和补棱柱中的超欧拉图

对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.     

关于判定超欧拉图的收缩法

P.A.Catlin提出一个问题：设H是图G的一个连通子图，如果G关于H的收缩图G/H有一个欧拉生成子图，那么在什么条件下G也有一个欧拉生成子图？研究了这一问题，讨论了Catlin提出的用收缩法判定超欧拉图的两个定理，给出了一些实用的超欧拉图的判别方法。     

超欧拉图判定方法的一个注记

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

超欧拉图的一个注记

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

3-方体的一个性质

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

一类特殊本原不可幂定号有向图的广义基

要考虑了一类含有3个圈(其中两个圈的长度相等但不相交)的本原不可幂定向有向图.通过分析图中是否存在寻求的途径及SSSD途径对,运用本原不可幂定号有向图和Frobenius数的性质及定义,给出了此类图中两个特殊图的广义本原指数和广义基.     

3-方体的一个性质

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

关于Catlin-猜想的反例

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

关于Euler生成子图极大边数的一个注记

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

极大欧拉生成子图边数的几个定理

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

超欧拉图生成子图边数问题的综述

综述了超欧拉图的生成子图边数问题,包括该问题的提出及研究发展过程,并罗列了两类公开问题:能否证明边数问题的下确界是35,若不能证明,能否找到更小的下确界?对一些著名的超欧拉图类,如具有两棵边不交的生成树的图等,能否证明其满足Catlin-猜想或35-猜想?     

一类超欧拉有向图中的超欧拉bypass

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.     

超双爪无关图的可折叠性(英文)

称图G是一个超爪,如果它同构于完全二部图K1,2。连接两个超爪的二度顶点而得到的图称为超双爪。一个图称为是超双爪无关图的,如果它没有导出的超双爪。证明了一个连通超双爪无关图的二部图G,当δ(G)≥4时是可折叠的,显然G是超欧拉的。最后,猜测定理1.1和1.2中的条件δ(G)≥4是最优的。     

边-超欧拉图的一个度数和条件

图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．     

关于Catlin的2／3—猜想

表示一个图,若Ｇ有一个欧拉生成图,则称Ｇ是超欧拉图。Ｃａｔｌｉｎ的２／３－猜想：设Ｇ是超欧拉图,Ｇ≠Ｋ１,则Ｇ存在一个欧拉生成子图Ｈ,使得Ｅ（Ｈ）／Ｅ（Ｇ）≥２／３。笔者证明了对于Ｃａｙｌｅｙ图,猜想成立。     

关于Catlin-猜想的一个定理

文献 [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)有平凡分支     

关于Catlin—猜想的一个定理

文献[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）有平凡分支。     

一类含两棵边不相交生成树的图

若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.     

关于Catlin的2/3—猜想

G表示一个图 ,若G有一个欧拉生成子图 ,则称G是超欧拉图。Catlin的 2 3—猜想 :设G是超欧拉图 ,G ≠K1,则G存在一个欧拉生成子图H ,使得｜E(H) ｜ ｜E(G) ｜≥ 2 3。笔者证明了对于Cayley图 ,猜想成立。