Supereulerian 3-path-quasi-transitive digraphs

摘要

A digraph D is supereulerian if D contains a spanning eulerian subdigraph. For any distinct four vertices c1, c2, c3, c4 of D, D is H1-quasi-transitive if c1 → c2 ← c3 ← c4, c1 and c4 are adjacent; D is H2-quasi-transitive if c1 ← c2 → c3 → c4, c1 and c4 are adjacent; D is H3-quasi-transitive if c1 → c2 → c3 → c4, c1 and c4 are adjacent; D is H4-quasi-transitive if c1 → c2 ← c3 → c4, c1 and c4 are adjacent. There are four distinct possible orientations of a 3-path, therefore we will refer to Hi-quasi-transitive digraphs as 3-path-quasi-transitive digraphs for convenience, where i ∈ [4]. Bang–Jensen et al conjectured that if the arc-strong connectivity λ(D) of D is not smaller than its independence number α(D), then D is supereulerian. In this paper, we give a sufficient and necessary conditions involving 3-path-quasi-transitive digraphs to be supereulerian and prove that the conjecture is ture for 3-path-quasi-transitive digraphs.