三边连通超欧拉图的一个注记

A Note on the 3-Edge-Connected Supereulerian Graphs

中文关键词:  超欧拉图  可折叠子图  收缩图  3边连通.

英文关键词:supereulerian  collapsible  reduction  3-edge-connected.

中文摘要:

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