{
  "id": "2012.03742",
  "version": "v1",
  "published": "2020-12-07T14:40:38.000Z",
  "updated": "2020-12-07T14:40:38.000Z",
  "title": "The smallest number of vertices in a 2-arc-strong digraph which has no good pair",
  "authors": [
    "Ran Gu",
    "Gregory Gutin",
    "Shasha Li",
    "Yongtang Shi",
    "Zhenyu Taoqiu"
  ],
  "comment": "56 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-07T14:40:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "smallest number",
      "independence number",
      "arc-strong digraph",
      "arc-connectivity",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 56,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}