J. Bang‐Jensen, Y. Wang

Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
Save to CiteDrive Show PDF

AbstractAn out‐branching (in‐branching ) in a digraph is a connected spanning subdigraph of in which every vertex except the vertex , called the root, has in‐degree (out‐degree) one. It is well known that there exists a polynomial algorithm for deciding whether a given digraph has arc‐disjoint out‐branchings with prescribed roots ( is part of the input). In sharp contrast to this, it is already NP‐complete to decide if a digraph has one out‐branching which is arc‐disjoint from some in‐branching. A digraph is semicomplete if it has no pair of nonadjacent vertices. A tournament is a semicomplete digraph without directed cycles of length 2. In this paper we give a complete classification of semicomplete digraphs that have an out‐branching which is arc‐disjoint from some in‐branching where are prescribed vertices of . Our characterization, which is surprisingly simple, generalizes a complicated characterization for tournaments from 1991 by the first author and our proof implies the existence of a polynomial algorithm for checking whether a given semicomplete digraph has such a pair of branchings for prescribed vertices and construct a solution if one exists. This confirms a conjecture of Bang‐Jensen for the case of semicomplete digraphs.

Need a simple solution for managing your BibTeX entries? Explore CiteDrive!

  • Web-based, modern reference management
  • Collaborate and share with fellow researchers
  • Integration with Overleaf
  • Comprehensive BibTeX/BibLaTeX support
  • Save articles and websites directly from your browser
  • Search for new articles from a database of tens of millions of references
Try out CiteDrive

More from our Archive