A Note on the 3-Edge-Connected Supereulerian Graphs

DOI：10.3770/j.issn:1000-341X.2010.05.025

 作者 单位 李宵民 重庆工商大学数学与统计学院, 重庆 400067 李登信 重庆工商大学数学与统计学院, 重庆 400067

对于两个整数 $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.