Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2 - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Graph Theory Year : 2022

Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2

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.
Fichier principal
Vignette du fichier
jgt.22779.pdf (436.6 Ko) Télécharger le fichier

Dates and versions

lirmm-04032263 , version 1 (16-03-2023)

Identifiers

Cite

Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo. Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2. Journal of Graph Theory, 2022, 100 (2), pp.294-314. ⟨10.1002/jgt.22779⟩. ⟨lirmm-04032263⟩
29 View
37 Download

Altmetric

Share

More