论文标题
独立2号的无分离跨越树木和分支
Non-separating spanning trees and out-branchings in digraphsof independence number 2
论文作者
论文摘要
图G =（v，e）的一个子图H =（V，f）如果G-F（即通过删除F中的边缘获得的图形获得）连接的图形是不分开的。类似地，我们说，如果D-B强烈连接，则D =（V，a）的X =（V，B）是不分开的。 We study non-separating spanning trees and out-branchings in digraphs of independence number 2. Our main results are that every 2-arc-strong digraph D of independence number alpha(D) = 2 and minimum in-degree at least 5 and every 2-arc-strong oriented graph with alpha(D) = 2 and minimum in-degree at least 3 has a non-separating out-branching and minimum in-degree 2还不够。我们还证明了许多其他结果，包括每2个arc-strong Digraph d具有alpha（d）<= 2，至少14个顶点具有非分离的跨性别树，并且每个图形g具有delta（g）> = 4和alpha（g）= 2的每个图形G的汉密尔顿路径不可分割。
A subgraph H= (V, F) of a graph G= (V,E) is non-separating if G-F, that is, the graph obtained from G by deleting the edges in F, is connected. Analogously we say that a subdigraph X= (V,B) of a digraph D= (V,A) is non-separating if D-B is strongly connected. We study non-separating spanning trees and out-branchings in digraphs of independence number 2. Our main results are that every 2-arc-strong digraph D of independence number alpha(D) = 2 and minimum in-degree at least 5 and every 2-arc-strong oriented graph with alpha(D) = 2 and minimum in-degree at least 3 has a non-separating out-branching and minimum in-degree 2 is not enough. We also prove a number of other results, including that every 2-arc-strong digraph D with alpha(D)<=2 and at least 14 vertices has a non-separating spanning tree and that every graph G with delta(G)>=4 and alpha(G) = 2 has a non-separating hamiltonian path.
