A Note on the 3-Edge-Connected Supereulerian Graphs
Received:August 19, 2008  Revised:June 30, 2009
Key Word: supereulerian   collapsible   reduction   3-edge-connected.  
Fund ProjectL:Supported by the Science Foundation of Chongqing Education Committee (Grant No.KJ100725).
Author NameAffiliation
Xiao Min LI School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, P. R. China 
Deng Xin LI School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, P. R. China 
Hits: 2200
Download times: 1995
Abstract:
      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.
Citation:
DOI:10.3770/j.issn:1000-341X.2010.05.025
View Full Text  View/Add Comment  Download reader