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

Some graphs which contain two edge-disjoint spanning trees

作　　者：李登信[1] 

机构地区：[1]重庆工商大学数学与统计学院,重庆400067

出　　处：《重庆工商大学学报（自然科学版）》2008年第3期223-225,共3页Journal of Chongqing Technology and Business University:Natural Science Edition

基　　金：重庆市自然科学基金(CSTC.2007BA2024);重庆市教委项目资助(KJ0707010)

摘　　要：若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.A graph G is supereulerian if G has a spanning eulerian subgraph. The author used SL to denote the family of all supereulerian graphs. In 1995, Zhi - Hong Chen and Hong - Jian Lai presented the following open problem ： Determine：L=min max G∈SL-{Kl}{｜E（H）/E（G）｜：H is a spanning eulerian subgraph of G}. In this note,the author defined the graphs Fi （i = 1,2,3 ） which contain two edge -disjoint spanning trees, and proved that if G∈ F3 ,then L≥2/3.

关 键 词：生成树 欧拉生成子图 收缩 边数 

分 类 号：O157.5[理学—数学]