判定超欧拉图的一个新方法

引入图的顶点的一种变换,使变换后的图顶点数不变,但边数减少;同时给出变换后的图与原图的超欧拉性的关系,从而得到判定超欧拉图的一个方法.该方法不仅可用于一般图的超欧拉性的判定,也可用于简化图的超欧拉性的判定.

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

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

寻找欧拉生成子图最大边数的一个方法

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

超欧拉图的一个注记

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

关于超欧拉图的一个注记

设G是无向无环的有限图 ,若G有一个生成子图是欧拉图 (Euler) ,则称G是超欧拉图 (Supereulerian) .本文不利用收缩方法 ,直接证明了 :当图G至多差一边有两棵边不相交的生成树时 ,G是超欧拉图或者G有割边 .

超欧拉图生成子图边数问题的综述(英文)

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

极大欧拉生成子图为Hamilton圈的图

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

无爪图的极大欧拉生成子图边数问题

研究了无爪图的极大欧拉生成子图边数问题,给出了当其最小度不小于4,且去掉极大欧拉生成子图后图的分支数不小于顶点数的1/4时,catlin-猜想成立;进一步得到了最大度不小于5时,超欧拉无爪图的极大欧拉生成子图一定不是Ham iltion圈的结论.

欧拉母图的树数条件

称含有生成欧拉子图的图为欧拉母图,F(G)表示为使图 G 含有两个边不交的生成树所要加入 E(G)中的最少边数.本文的结果是:如果3边连通图 G 满足①F(G)≤2或②F(G)=3,G 含4圈和 G 的任一非平凡真子图都不可折,则 G 是欧拉母图.

一类有向欧拉图的优美性

研究了有向欧拉图，证明了，优美的必要条件，并且证明了和的优美性．

探索Euler生成子图边数的一种方法

关于超欧拉图的欧拉生成子图 (spanning eulerian subgraph) 的边数问题,P.A.Catlin 、Hong- Jian Lai、Zhi-Hong Chen 等人提出若干问题。本文给出了探索超欧拉图的欧拉生成子图边数的 一种方法。

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

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

一类α-子图

根据相关文献中给出的用以寻找欧拉生成子图极大边数的有效工具α-子图的概念,证明了对于任意G∈SL,Kl,m(l≥3,m≥3)是G的1-min{1l,m}-子图.

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．

寻找哈密尔顿函数图形的周期

判定一个图形是否是哈密尔顿函数是一个公开的难题。本文里,这一难题被转化为判断一个图形是否有一个两个规则哈密尔顿函数生成的子图。同时,还将介绍这一方法的应用过程,这可直接运用于计算机。

加三角形的圈的优美性

本文研究加三角形的圈的优美性,证明了两类图 C_n(p,q,2)、C_n(p,q,3)的优美性。

关于Catlin的2/3—猜想

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

一类用于寻找欧拉生成子图边数的收缩子图

结合可折叠子图给出了可折叠α-子图的概念,得到可折叠α-子图一定为α-子图,并得到可折叠α-子图的顶点有交且边不交的并仍为可折叠α-子图.同时得到至多差1边具有3棵边不交的生成树的图和K_(l,m)(l≥3,m≥3)均是可折叠2/3-子图,并给出其在寻找欧拉生成子图极大边数的应用,同时也得到了一种寻找α-子图的方法.

3-方体的一个性质

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

Connected Eulerian Spanning Subgraphs

We prove that if G is a 2-edge-connected simple graph with p verti- ces and at least +7 edges,then G other than the complete bipartite graph K_(2,5) has a connected eulerian spanning subgraph and also give all the six extremal graphs with ()+6 edges and edge connectivety K'(G)=2.