TY - JOUR

T1 - Strengthened Ore conditions for (s,t)-supereulerian graphs

AU - Lei, Lan

AU - Li, Xiaoming

AU - Wu, Yang

AU - Zhang, Taoye

AU - Lai, Hong Jian

N1 - Funding Information:
This research is partially supported by General Project of Natural Science Foundation of Chongqing , China (No. cstc2019jcyj-msxmX0579 ) and by National Natural Science Foundation of China grants (Nos. 11771039 , 11771443 ).
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/10/30

Y1 - 2022/10/30

N2 - 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 [Formula presented], when n is sufficiently large, is (0,0)-supereulerian or is contractible to K2,3. A function j0(s,t) has been found that every (s,t)-supereulerian graph must have edge connectivity at least j0(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)≥j0(s,t) and if for any nonadjacent vertices u,v∈V(G), dG(u)+dG(v)≥αn+β, then either G is (s,t)-supereulerian, or G is contractible to a member in F(α,β;s,t). (ii) If κ′(G)≥j0(s,t) and if for any nonadjacent vertices u,v∈V(G), dG(u)+dG(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 for any vertices u,v,w∈V(G) with E(G[{u,v,w}])=0̸, dG(u)+dG(v)+dG(w)>n−3. then G is (s,t)-supereulerian if and only if κ′(G)≥j0(s,t).

AB - 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 [Formula presented], when n is sufficiently large, is (0,0)-supereulerian or is contractible to K2,3. A function j0(s,t) has been found that every (s,t)-supereulerian graph must have edge connectivity at least j0(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)≥j0(s,t) and if for any nonadjacent vertices u,v∈V(G), dG(u)+dG(v)≥αn+β, then either G is (s,t)-supereulerian, or G is contractible to a member in F(α,β;s,t). (ii) If κ′(G)≥j0(s,t) and if for any nonadjacent vertices u,v∈V(G), dG(u)+dG(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 for any vertices u,v,w∈V(G) with E(G[{u,v,w}])=0̸, dG(u)+dG(v)+dG(w)>n−3. then G is (s,t)-supereulerian if and only if κ′(G)≥j0(s,t).

UR - http://www.scopus.com/inward/record.url?scp=85131821995&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131821995&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.05.003

DO - 10.1016/j.dam.2022.05.003

M3 - Article

AN - SCOPUS:85131821995

SN - 0166-218X

VL - 320

SP - 68

EP - 80

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -