Back to Search Start Over

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

Authors :
Jørgen Bang‐Jensen
Stéphane Bessy
Frédéric Havet
Anders Yeo
University of Southern Denmark (SDU)
Algorithmes, Graphes et Combinatoire (ALGCO)
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
Combinatorics, Optimization and Algorithms for Telecommunications (COATI)
Inria Sophia Antipolis - Méditerranée (CRISAM)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED)
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
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.

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⟩