z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom