Strengthened Ore conditions for [formula omitted]-supereulerian graphs.

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 (1979) 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 (Catlin, 1988) 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. A function j 0 (s , t) has been found that every (s , t) -supereulerian graph must have edge connectivity at least j 0 (s , t). For any nonnegative integers s and t , we obtain best possible Ore conditions to assure a simple graph on n vertices to be (s , t) -supereulerian as stated in the following. (i) For any real numbers α and β with 0 < α < 1 , there exists a family of finitely many graphs F (α , β ; s , t) such that if κ ′ (G) ≥ j 0 (s , t) and if for any nonadjacent vertices u , v ∈ V (G) , d G (u) + d G (v) ≥ α n + β , then either G is (s , t) -supereulerian, or G is contractible to a member in F (α , β ; s , t). (ii) If κ ′ (G) ≥ j 0 (s , t) and if for any nonadjacent vertices u , v ∈ V (G) , d G (u) + d G (v) ≥ n − 1 , then when n is sufficiently large, either G is (s , t) -supereulerian, or G is contractible to one of the six well specified graphs. (iii) Suppose that δ (G) ≥ 5. If (1) for any vertices u , v , w ∈ V (G) with E (G [ { u , v , w } ]) = 0̸ , d G (u) + d G (v) + d G (w) > n − 3. then G is (s , t) -supereulerian if and only if κ ′ (G) ≥ j 0 (s , t). [ABSTRACT FROM AUTHOR]