《Euler生成子图极大边数的一些结果与问题》由会员分享，可在线阅读，更多相关《Euler生成子图极大边数的一些结果与问题（4页珍藏版）》请在金锄头文库上搜索。
1、Eule生成子图极大边数的一些结果与问题李登信 李宵民（重庆工商大学数学与统计学院,重庆4007）用表示图的奇顶点组成的集合,的图称为偶图 ；连通的偶图称为欧拉图。图存在欧拉生成子图,则称是超欧拉图（suprulerian）。我们常用表示全体超欧拉图组成的集合。早在1983年，Bemon,acon，aeger等人得到了如下结果：定理 每个边连通图都存在偶子图，使得.1关于ule生成子图的极大边数问题,P。A atlin注意到正则图的情形，曾经猜想:若是超欧拉图，则存在一个欧拉生成子图，使得. 21995年，赖虹建（Hngin)、陈志宏（ZhiHong Chn)等人提出如下公开问题3问题决定 0
2、年，我们在3中给出例子说明。在文献4中，我们提出猜想：猜想1设是简单图,则。问题2 是否存在超欧拉图，有一个极大（边数最多）欧拉生成子图，使得？1 关于的一些结果定理1 对于简单图图G（非欧拉图）,若存在一个极大欧拉生成子图H,使得E（H)/（G）=,则一定存在图G，使得（)|(G）|，其中*为的极大欧拉生成子图。（03年，)定理1说明:不可达到。定理 设是超欧拉图,表示图的奇顶点组成的集合，。下列每一个断言成立：（2005年，6）（1） 若，是简单图,则。（2） 若，是简单图，则。（3） 若允许有重边，则。定理3 设是有个点的简单图,。如果 ，且,则。（2006年，)对于超欧拉图有下列著名定
3、理8：定理 4 若图含两棵边不相交的生成树,则是超欧拉图.我们曾提出如下问题：猜想2：设是简单图，含两棵边不相交的生成树,则存在一个欧拉生成子图,使得。的任若，含两棵边不相交的生成树,则。增加一个点,设是意两个点，增加两条边，于是得到个点的含两棵边不相交的生成树的图，记为。类似地可得个点的含两棵边不相交的生成树的图,如此类推可得个点的含两棵边不相交的生成树的图。参见图1。 图 的构成设.在构造的过程中，用表示中的两个点，表示在中增加的一个点，即，。若在构造的过程中，用表示中的两个相邻点，表示在中增加的一个点,则得到的一个子集。即其中，。我们得到下列结果：定理5 若图,则。猜想3 若图，则。2用
4、收缩方法来估计设H是的子图,图G关于子图H的收缩定义为:在G中,把的点收缩为一个点，去掉H的边,得到G关于子图H的收缩，记为。因为欧拉图的收缩仍为欧拉图，下列结论是显然的。定理6设H是图G的子图,G是超欧拉图，则也是超欧拉图。设X是G的子图,.令因为图比图简单,自然想到:可否用来估计？于是我们有下列问题。问题3 设G是超欧拉图，是G的子图，。当满足什么条件时，由可推出？这里为给定的常数。 为了研究问题2，我们引入下列定义：定义1 设G是超欧拉图，是的子图,，为给定的常数。若可推出，则称子图X是G的一个-子图。设H是图G的子图,我们用表示去掉H中的任意条边而得到的图.对于子图，我们得到一些结果。
5、定理 完全图、完全二分图是子图。定理8 是子图。定理 是子图。定理10 是-子图。问题4 决定使 是子图或子图。显然，确定更多的子图,对于估计ule生成子图的极大边数是有意义的。参考文献 Bermd，Jckso，and Jaeer,JCbinara heory，er。3(983)297-382 H.J. Lai， Lectue Noteon Supereuleria rs and Reated ocs, 19。3 .。 Chn, H Li， Reduction technqsr sperulian grphsand rlatd opics-an udat， in： Ku Tung-Hn(),C
6、omnators and rahToy95， Word Sentii, ingapore, London， 199， pp.5364 Dngxin ， Deyng Li， Jingzg Mao， maxum nmber ofegesin sanninguleran suraph，icre Matemaics 272（200） 930 李霄民，李登信， 探索极大欧拉生成子图的一种方法,工程数学学报，21（2004)0180206 Dngxi Li，Te Maxmm NmbeofEdgeof a Spanning Eulerian ugraph n a Grah,rs Combinaoris,(acepted ）oapear7 李登信,关于uler生成子图极大边数的一个注记，重庆工商大学学报（自科版），06,20(）:158 P. A. Catlin，Aredtion metod t find paningeurian subras， J。fGr Theor, Vol1，o.,2924.n MaxiuNmberofEdges in a Spnning uleria Subgraph Linxn iXiaomin （Cogqinehnogy nd usiness Uiverity, Chongg 4067）文中如有不足，请您指教！ /
