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

• 作 者: 李登信
• 机 构: 重庆工商大学数学与统计学院
• 出 处: 重庆工商大学学报：自然科学版
• 发表日期: 2008年3期
• 关键词: 生成树 欧拉生成子图 收缩 边数 spanning tree spanning eulerian subgraph contraction number of
• 基金项目: 重庆市自然科学基金（CSTC.2007BA2024）及重庆市教委项目资助（KJ0707010）.

若G有一个生成子图是欧拉图，则称G是超欧拉图（supereulerian graph）．用SL表示全体超欧拉图的集合．1995年，赖虹建（LAI Hong—jian）、陈志宏（CHEN Zhi—hong）提出一个关于欧拉生成子图边数的公开问题；决定：L=min max G∈SL-{Kl}{｜E（H）/E（G）｜：H是G的欧拉生成子图}．定义了一些含两棵边不相交生成树的图Fi（i=1，2，3），证明了如果G∈F3.那么L≥2/3．