Name
Abstract | ||
|---|---|---|
We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching B + and an in-branching B - 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 D 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1002/jgt.22779 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
arc-connectivity, arc-disjoint branchings, digraphs of independence number 2, in-branching, out-branching | Journal | 100 |
Issue | ISSN | Citations |
2 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bang-Jensen Joergen | 1 | 0 | 0.34 |
| Stéphane Bessy | 2 | 117 | 19.68 |
| Frédéric Havet | 3 | 433 | 55.15 |
| Anders Yeo | 4 | 1225 | 108.09 |