Department of Mathematics, West Virginia University, P.O. Box. 6310, Morgantown, WV 26506, USA
Abstract:
For an integer l0, define
to be the family of graphs such that
if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in
are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in
. Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in J. Graph Theory 1 (1977) 79–84] and J. Graph Theory 3 (1979) 91–93] are extended.