论文标题
独立数字的弧形内和外分支最多2
Arc-disjoint in- and out-branchings in digraphs of independence number at most 2
论文作者
论文摘要
我们证明，独立号码的每个挖掘都至少为2，并且至少有2个具有分支的$ b^+$和一个分支机构的$ b^ - $是Arc-Dischoint（我们称之为分支很好）。 就弧形连接性而言，这是最好的，因为有无限的强大挖掘图，具有独立性2，并且任意高的最小值和超级距离，并且没有良好的配对。结果解决了托马森（Thomassen）对独立数2的挖掘的猜想。我们证明，最多6个顶点的每个挖掘物和弧连接性至少有2个具有很好的对，并给出了一个不好的独立4的10个带有不错的独立4的顶点的2- arc-strong digraph $ d $。我们还表明，有许多独立性7和电弧连接性2的无限挖掘纸没有好对。最后，我们提出了许多开放问题。
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 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 good no 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.
