Supereulerian Graphs and the Petersen Graph

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...

Full description

Saved in:
Bibliographic Details
Published in:Acta mathematica Sinica. English series 2014-02, Vol.30 (2), p.291-304
Main Authors: Li, Xiao Min, Lei, Lan, Lai, Hong-Jian, Zhang, Meng
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Mathematical models
Mathematics
Mathematics and Statistics
Petersen图
Studies
Theorems
丝氨酸
图论
欧拉生成子图
超欧拉图
连通图
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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）].
ISSN:1439-8516
1439-7617
DOI:10.1007/s10114-014-2272-y