Supereulerian bipartite digraphs. Issue 1 (6th February 2018)

• Record Type: Journal Article
• Authors: Zhang, Xindong; Liu, Juan; Wang, Lan; Lai, Hong‐Jian
• Is Part Of: Journal of graph theory. Volume 89:Issue 1(2018)
• Page Start: 64
• Page End: 75
• Publication Date: 2018-02-06
• Subjects: arc‐strong connectivity -- eulerian digraph -- independence number -- matching number -- supereulerian bipartite digraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22240
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity λ ( D ) of a digraph D is not less than the independence number α ( D ), then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let α ′ ( D ) be the size of a maximum matching of D . We prove that if D is a bipartite digraph satisfying λ ( D ) ≥ ⌊ α ′ ( D ) 2 ⌋ + 1, then D is supereulerian. Consequently, every bipartite digraph D satisfying λ ( D ) ≥ ⌊ α ( D ) 2 ⌋ + 1 is supereulerian. The bound of our main result is best possible.