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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom