| 李宵民,李登信.三边连通超欧拉图的一个注记[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). |
|
| 摘要点击次数: 2398 |
| 全文下载次数: 2075 |
| 中文摘要: |
| 对于两个整数 $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阅读器 |
