李宵民,李登信.三边连通超欧拉图的一个注记[J].数学研究及应用,2010,30(5):944~946
三边连通超欧拉图的一个注记
A Note on the 3-Edge-Connected Supereulerian Graphs
投稿时间:2008-08-19  最后修改时间:2009-06-30
DOI:10.3770/j.issn:1000-341X.2010.05.025
中文关键词:  超欧拉图  可折叠子图  收缩图  3边连通.
英文关键词:supereulerian  collapsible  reduction  3-edge-connected.
基金项目:重庆市教育委员会科技项目(Grant No.KJ100725).
作者单位
李宵民 重庆工商大学数学与统计学院, 重庆 400067 
李登信 重庆工商大学数学与统计学院, 重庆 400067 
摘要点击次数: 1284
全文下载次数: 1222
中文摘要:
      对于两个整数 $l>0$ 和 $k\geq 0$,用$C(l,k)$ 表示一类2-边连通的图,图$G\in C(l,k)$ 当且仅当对于任意至多含有3条边的边割 $S\subseteq E(G)$, $G-S$的每个分支至少有 $(|V(G)|-k)/l$个顶点.本文证明了如果3-边连通的简单图 $G\in C(10,3)$, 则 $G$ 是超欧拉图当且仅当$G$ 不能收缩为Petersen图. 此结果推广了陈志宏在[Supereulerian graphs and Petersen graph. JCMCC 9 (1991) 79-89]中的结果.
英文摘要:
      For two integers $l>0$ and $k\geq 0$, define $C(l,k)$ to be the family of 2-edge connected graphs such that a graph $G\in C(l,k)$ if and only if for every bond $S\subseteq E(G)$ with $|S|\leq 3$, each component of $G-S$ has order at least $(|V(G)|-k)/l$. In this note we prove that if a 3-edge-connected simple graph $G$ is in $C(10,3)$, then $G$ is supereulerian if and only if $G$ cannot be contracted to the Petersen graph. Our result extends an earlier result in [Supereulerian graphs and Petersen graph. JCMCC 1991, 9: 79-89] by Chen.
查看全文  查看/发表评论  下载PDF阅读器