Euler生成子图极大边数的一些结果与问题|江阴雨辰互联

2023年7月19日发(作者：)

Euler生成子图极大边数的一些结果与问题

李登信李宵民

（重庆工商大学数学与统计学院，重庆400067）

用O(G)表示图G的奇顶点组成的集合，O(G)的图称为偶图；连通的偶图称为欧拉图。图G存在欧拉生成子图，则称G是超欧拉图（supereulerian）。我们常用SL表示全体超欧拉图组成的集合。

早在1983年，Bermond,Jackson,Jaeger等人得到了如下结果：

定理每个2-边连通图G都存在偶子图H，使得|E(H)|2。[1]

|E(G)|3关于Euler生成子图的极大边数问题， P. A. Catlin 注意到3-正则图的情形，曾经猜想：若G是超欧拉图，则G存在一个欧拉生成子图H，使得|E(H)|2。 [2]

|E(G)|31995年，赖虹建（Hong-Jian Lai）、陈志宏（Zhi-Hong Chen）等人提出如下公开问题[3]

|E(H)|:H是G的一个Euler生成子图} 问题1 决定

Lminmax{GSL{K1}|E(G)|2001年，我们在[3]中给出例子说明L<猜想1 设G是简单图，则L2。在文献[4]中，我们提出猜想：

33。

5问题2 是否存在超欧拉图G，G有一个极大（边数最多）欧拉生成子图H，使得|E(H)|3？

|E(G)|5

1 关于L的一些结果

定理1 对于简单图图G（非欧拉图），若存在一个极大欧拉生成子图H，使得|E(H)|/|E(G)|=α，则一定存在图G*，使得|E(H*)|/|E(G*)|<α，其中H*为G*的极大欧拉生成子图。（2003年，[5]）

定理1说明：L不可达到。

定理2 设G是超欧拉图，O(G)表示图G的奇顶点组成的集合，|O(G)|2k。下列每一个断言成立：（2005年，[6]）

（1）若k3，G是简单图，则L2。

3（2）若k4，G是简单图，则L（3）若G允许有重边，则L3。

51。

2n1

(b{4,5})，且b定理3 设G是有n个点的简单图，GSL。如果(G)3。（2006年，[7]）

5对于超欧拉图有下列著名定理[8]：

定理 4 若图G含两棵边不相交的生成树，则G是超欧拉图。

我们曾提出如下问题：

猜想2：设G是简单图，G含两棵边不相交的生成树，则G存在一个欧拉生成子n4b，则L图H，使得|E(H)|2。

|E(G)|3的任若|V(G)|4，G含两棵边不相交的生成树，则GK4。增加一个点v，设u,w是K4意两个点，增加两条边vu,vw，于是得到5个点的含两棵边不相交的生成树的图，记为G5。类似地可得6个点的含两棵边不相交的生成树的图G6，如此类推可得n个点的含两棵边不相交的生成树的图Gn。参见图1。

图1

Gn的构成

设F1{Gi|i4}。

在构造Gn的过程中，用ui,wi表示Gi中的两个点，vi1表示在Gi中增加的一个点，即

Gi1Gi{vi1ui,vi1wi}，ui,wiV(Gi),vi1V(Gi),i4，G4K4。

若在构造Gn的过程中，用ui,wi表示Gi中的两个相邻点，vi1表示在Gi中增加的一个点，则得到F1的一个子集F2。即

F2{Gi|i4,}

其中，Gi1Gi{vi1ui,vi1wi},uiwiE(Gi),G4K4。

2 我们得到下列结果：

2。

32猜想3 若图GF1，则L。

2 用收缩方法来估计L