On (s,t)-supereulerian graphs with linear degree bounds

Abstract For integers s ≥ 0 and t ≥ 0 , a graph G is ( s , t ) -supereulerian if for any disjoint edge sets X , Y ⊆ E ( G ) with | X | ≤ s and | Y | ≤ t , G has a spanning closed trail that contains X and avoids Y . Pulleyblank in [J. Graph Theory, 3 (1979) 309-310] showed that determining whether a graph is ( 0 , 0 ) -supereulerian, even when restricted to planar graphs, is NP-complete. Settling an open problem of Bauer, Catlin in [J. Graph Theory, 12 (1988) 29–45] showed that every simple graph G on n vertices with δ ( G ) ≥ n 5 − 1 , when n is sufficiently large, is ( 0 , 0 ) -supereulerian or is contractible to K 2 , 3 . We prove the following for any nonnegative integers s and t . (i) For any real numbers a and b with 0 a 1 , there exists a family of finitely many graphs F ( a , b ; s , t ) such that if G is a simple graph on n vertices with κ ′ ( G ) ≥ t + 2 and δ ( G ) ≥ a n + b , then either G is ( s , t ) -supereulerian, or G is contractible to a member in F ( a , b ; s , t ) . (ii) Let l K 2 denote the connected loopless graph with two vertices and l parallel edges. If G is a simple graph on n vertices with κ ′ ( G ) ≥ t + 2 and δ ( G ) ≥ n 2 − 1 , then when n is sufficiently large, either G is ( s , t ) -supereulerian, or for some integer j with t + 2 ≤ j ≤ s + t , G is contractible to a j K 2 .