 Supereulerian 3-path-quasi-transitive digraphsChangchang Dong, Juan Liu and Jixiang Meng Applied Mathematics and Computation, 2020, vol. 372, issue C Abstract: 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. Keywords: Supereulerian digraph; Spanning closed ditrail; 3-path-quasi-transitive digraph; Arc-strong connectivity; Independence number; Eulerian factor (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:372:y:2020:i:c:s0096300319309567 DOI: 10.1016/j.amc.2019.124964 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.