Premium
Supereulerian bipartite digraphs
Author(s) -
Zhang Xindong,
Liu Juan,
Wang Lan,
Lai HongJian
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22240
Subject(s) - digraph , bipartite graph , combinatorics , mathematics , matching (statistics) , complete bipartite graph , discrete mathematics , graph , statistics
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.