首页 | 本学科首页   官方微博 | 高级检索  
     


Supereulerian bipartite digraphs
Abstract:A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity urn:x-wiley:03649024:media:jgt22240:jgt22240-math-0001 of a digraph D is not less than the independence number urn:x-wiley:03649024:media:jgt22240:jgt22240-math-0002, then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let urn:x-wiley:03649024:media:jgt22240:jgt22240-math-0003 be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying urn:x-wiley:03649024:media:jgt22240:jgt22240-math-0004, then D is supereulerian. Consequently, every bipartite digraph D satisfying urn:x-wiley:03649024:media:jgt22240:jgt22240-math-0005 is supereulerian. The bound of our main result is best possible.
Keywords:arc‐strong connectivity  eulerian digraph  independence number  matching number  supereulerian bipartite digraph
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号