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

Lan Lei, Xiaoming Li, Yang Wu, Taoye Zhang, Hong Jian Lai

Research output: Contribution to journalArticlepeer-review

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 (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).

Original languageEnglish (US)
Pages (from-to)68-80
Number of pages13
JournalDiscrete Applied Mathematics
Volume320
DOIs
StatePublished - Oct 30 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Strengthened Ore conditions for (s,t)-supereulerian graphs'. Together they form a unique fingerprint.

Cite this