Digital Commons Network^™

Supereulerian Graphs And The Petersen Graph, Ii, Zhi-Hong Chen, Hong-Jian Lai

Scholarship and Professional Work - LAS

In this note, we verify two conjectures of Catlin in [J. Graph Theory 13 (1989) 465 - 483] for graphs with at most 11 vertices. These are used to prove the following theorem which improves prior results in [10] and [13]:

Let G be a 3-edge-connected simple graph with order n. If n is large and if for every edge 11.v E E(G), d(u) + d(v) 2 % - 2, then either G has a spanning eulerian subgraph or G can be contracted to the Petersen graph.