极小3边连通可折图

本文证实了Catlin和赖虹建的猜想:设G是非平凡连通简化图,如果F(G)=2,则G∈{K_2,(?)t≥1}.

欧拉母图的树数条件

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

一类具有生成闭迹的图

1987年,P.Paulraja在[2]中给出如下猜想:如果G是a(G)≥3的2-连通图,且G的每条边均属于长为3或4的圈。则G有生成闭迹。同年P.A.Catlin在[3]中猜测上述的G还是可折迭的(Collapsible)。本文给出了这两个猜想的证明。

超欧拉3边连通图的边数

若图G含有生成欧拉子图,则称G是超欧拉的。本文证明了3边连通简单图G,如果|E（G）|≥（|V（G）|-9 2）+16,那么G是超欧拉的;进一步,如果不含K3且|E（G）|≥（|V（G）|-9）2/4+18,则G也是超欧拉的.

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

对于一个图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是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.

3-edge-connected Supereulerian Graphs

This paper shows three sufficient conditions for a 3-edge-connected simple graph to be supereulerian.