The smallest number of vertices in a 2-arc-strong digraph which has no good pair

2020/12/07 by Ran Gu, Gu, Ran, Gregory Gutin +7
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2012.03742

openalex publication_date 2020/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Bang-Jensen, Bessy, Havet and Yeo showed 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 (such two branchings are called a \it good pair), which settled a conjecture of Thomassen for digraphs of independence number 2. They also proved that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and gave an example of a 2-arc-strong digraph D on 10 vertices with independence number 4 that has no good pair. They asked for the smallest number n of vertices in a 2-arc-strong digraph which has no good pair. In this paper, we prove that every digraph on at most 9 vertices and arc-connectivity at least 2 has a good pair, which solves this problem.

Related

• Arc-disjoint in- and out-branchings in digraphs of independence number at most 2
• Arc-disjoint in- and out-branchings in semicomplete split digraphs
• Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
• Arc-disjoint out- and in-branchings in compositions of digraphs
• Arc-Disjoint Paths and Trees in 2-Regular Digraphs