Abstract
We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching (Formula presented.) and an in-branching (Formula presented.) which are arc-disjoint (we call such branchings a good pair). This is best possible in terms of the arc-connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in- and out-degrees that have no good pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and give an example of a 2-arc-strong digraph (Formula presented.) on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc-connectivity 2 that have no good pair. Finally we pose a number of open problems.
| Original language | English |
|---|---|
| Pages (from-to) | 294-314 |
| Number of pages | 21 |
| Journal | Journal of Graph Theory |
| Volume | 100 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Jun 2022 |
Keywords
- arc-connectivity
- arc-disjoint branchings
- digraphs of independence number 2
- in-branching
- out-branching
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics