Back to Search
Start Over
Arc-disjoint in- and out-branchings in digraphs of independence number at most 2
- Source :
- Journal of Graph Theory, Journal of Graph Theory, 2022, 100 (2), pp.294-314. ⟨10.1002/jgt.22779⟩, Bang-Jensen, J, Bessy, S, Havet, F & Yeo, A 2022, ' Arc-disjoint in-and out-branchings in digraphs of independence number at most 2 ', Journal of Graph Theory, vol. 100, no. 2, pp. 294-314 . https://doi.org/10.1002/jgt.22779
- Publication Year :
- 2020
-
Abstract
- International audience; 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.
- Subjects :
- Mathematics::Combinatorics
in-branching
arc-disjoint branchings
out-branching
Computer Science::Discrete Mathematics
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
digraphs of independence number 2
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Arc-disjoint branchings
Combinatorics (math.CO)
arc-connectivity
Geometry and Topology
05c20
Subjects
Details
- Language :
- English
- ISSN :
- 03649024 and 10970118
- Database :
- OpenAIRE
- Journal :
- Journal of Graph Theory, Journal of Graph Theory, 2022, 100 (2), pp.294-314. ⟨10.1002/jgt.22779⟩, Bang-Jensen, J, Bessy, S, Havet, F & Yeo, A 2022, ' Arc-disjoint in-and out-branchings in digraphs of independence number at most 2 ', Journal of Graph Theory, vol. 100, no. 2, pp. 294-314 . https://doi.org/10.1002/jgt.22779
- Accession number :
- edsair.doi.dedup.....060e0192c539c7cc5dbaa13b2cf68f5c
- Full Text :
- https://doi.org/10.1002/jgt.22779⟩