摘要
图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e.给出了边-超欧拉图的一个度数和条件,即:设G是2-边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d(u)+d(v)≥52n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者Ge(G关于e的剖分图)可以被收缩成K2,3或K2,5.
A graph G is called edge-supereulerian if for any edge e in E（G）, there is a spanning eulerian subgraph H which contains e. In this paper, a degree-sum condition for edge-supereulerian graph is present, i. e. when G is a 2-edge-connected simple graph on n vertices, if n ≥ 100 and d（u） ＋d（v） ≥ 2/5n whenever u and v are not adjacent in G, then for any edge e in E（G） there is a spanning eulerian subgraph H of G that contains e, or G, （subdivided graph by e） can be contracted to K2.3 or K2.5.
出处
《西南师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2009年第1期16-19,共4页
Journal of Southwest China Normal University(Natural Science Edition)
基金
重庆市自然科学基金资助项目(CSTC,2007BA2024)
重庆工商大学青年基金资助项目(0752012)
关键词
边-超欧拉性
可折叠
简化图
边不交生成树
剖分
收缩
edge-supereulerian
collapsible
reduced graph
edge-disjoint spanning trees
subdividing
contracting
