Supereulerian Graphs and the Petersen Graph  

作　　者：Xiao Min LI Lan LEI Hong-Jian LAI Meng ZHANG 

机构地区：[1]Department of Mathematics and Statistics,Chongqing Technology and Business University [2]Department of Mathematics,West Virginia University [3]College of Mathematics and System Sciences,Xinjiang University

出　　处：《Acta Mathematica Sinica,English Series》2014年第2期291-304,共14页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant No.11001287);Science Foundation Chongqing Education Committee(Grant Nos.KJ100725 and KJ120731)

摘　　要：A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].

关 键 词：Supereulerian graphs petersen graph edge-cut REDUCTION CONTRACTION 

分 类 号：O157.5[理学—数学] Q517[理学—基础数学]