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

  • Jørgen Bang-Jensen
  • , Stéphane Bessy
  • , Frédéric Havet
  • , Anders Yeo

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)294-314
Number of pages21
JournalJournal of Graph Theory
Volume100
Issue number2
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Arc-disjoint in- and out-branchings in digraphs of independence number at most 2'. Together they form a unique fingerprint.

Cite this