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

Euler生成子图极大边数的一些结果与问题李登信 李宵民（重庆工商大学数学与统计学院，重庆400067）用表示图的奇顶点组成的集合，的图称为偶图 ；连通的偶图称为欧拉图。图存在欧拉生成子图，则称是超欧拉图（supereulerian）。我们常用表示全体超欧拉图组成的集合。早在1983年，Bermond,Jackson,Jaeger等人得到了如下结果：定理 每个2-边连通图都存在偶子图，使得。1关于Euler生成子图的极大边数问题， P. A. Catlin 注意到3-正则图的情形，曾经猜想：若是超欧拉图，则存在一个欧拉生成子图，使得。 21995年，赖虹建（Hong-Jian Lai）、陈志宏（Zhi-Hong Chen）等人提出如下公开问题3问题1 决定 2001年，我们在3中给出例子说明。在文献4中，我们提出猜想：猜想1 设是简单图，则。问题2 是否存在超欧拉图，有一个极大（边数最多）欧拉生成子图，使得？1 关于的一些结果定理1 对于简单图图G（非欧拉图），若存在一个极大欧拉生成子图H，使得|E(H)|/|E(G)|=，则一定存在图G*，使得|E(H*)|/|E(G*)|，其中H*为G*的极大欧拉生成子图。（2003年，5）定理1说明：不可达到。定理2 设是超欧拉图，表示图的奇顶点组成的集合，。下列每一个断言成立：（2005年，6）（1） 若，是简单图，则。（2） 若，是简单图，则。（3） 若允许有重边，则。定理3 设是有个点的简单图，。如果 ，且，则。（2006年，7）对于超欧拉图有下列著名定理8：定理 4 若图含两棵边不相交的生成树，则是超欧拉图。我们曾提出如下问题：猜想2：设是简单图，含两棵边不相交的生成树，则存在一个欧拉生成子图，使得。的任若，含两棵边不相交的生成树，则。增加一个点，设是意两个点，增加两条边，于是得到5个点的含两棵边不相交的生成树的图，记为。类似地可得6个点的含两棵边不相交的生成树的图，如此类推可得个点的含两棵边不相交的生成树的图。参见图1。 图1 的构成设。在构造的过程中，用表示中的两个点，表示在中增加的一个点，即，。若在构造的过程中，用表示中的两个相邻点，表示在中增加的一个点，则得到的一个子集。即其中，。我们得到下列结果：定理5 若图，则。猜想3 若图，则。2 用收缩方法来估计设H是G的子图，图G关于子图H的收缩定义为：在G中，把H的点收缩为一个点，去掉H的边，得到G关于子图H的收缩，记为。因为欧拉图的收缩仍为欧拉图，下列结论是显然的。定理6 设H是图G的子图，G是超欧拉图，则也是超欧拉图。设X是G的子图，。令因为图比图G简单，自然想到：可否用来估计？于是我们有下列问题。问题3 设G是超欧拉图，X是G的子图，。当X满足什么条件时，由可推出？这里为给定的常数。 为了研究问题2，我们引入下列定义：定义1 设G是超欧拉图，X是G的子图，为给定的常数。若可推出，则称子图X是G的一个子图。设H是图G的子图，我们用表示去掉H中的任意条边而得到的图。对于子图，我们得到一些结果。定理7 完全图、完全二分图是子图。定理8 是子图。定理9 是子图。定理10 是子图。问题4 决定 使 是子图或子图。显然，确定更多的子图，对于估计Euler生成子图的极大边数是有意义的。参考文献1 Bermond,Jackson,and Jaeger, J.Combinatorial Theory,Ser.B35(1983)297-3082 H.-J. Lai, Lecture Note on Supereulerian Graphs and Related Topics, 1996.3 Z.-H. Chen, H.-J. Lai, Reduction techniques for supereulerian graphs and related topics-an update, in: Ku Tung-Hsin(Ed), Combinatorics and Graph Teory95, World Scientific, ingapore, London, 1995, pp.53-69.4 Dengxin Li, Deying Li, Jingzhong Mao, On maximum number of edges in a spanning eulerian subgraph, Discrete Mathematics 272(2004) 299-302.5 李霄民，李登信， 探索极大欧拉生成子图的一种方法，工程数学学报，21（2004）1018-10206 Dengxin Li，The Maximum Number of Edges of a Spanning Eulerian Subgraph in a Graph，Ars Combinatoris，(accepted ) to appear.7 李登信，关于Euler生成子图极大边数的一个注记，重庆工商大学学报（自科版），2006，20（1）：1-58 P. A. Catlin, A reduction method to find spanning eulerian subgraphs, J. of Graph Theory, Vol.12,No.1,29-24.On Maximum Number of Edges in