论文标题
3边缘连接图的方向的连通性
Connectivity of orientations of 3-edge-connected graphs
论文作者
论文摘要
我们试图概括纳什 - 威廉姆斯的定理，以指出图形具有$ k $ -ARC连接的方向，并且仅当它是$ 2K $ - $ - 边缘连接的情况下。在牢固连接的Digraph中，我们称之为弧{\ it删除}，如果其删除留下了强烈连接的digraph。考虑到$ 3 $ - 边缘连接的图$ g $，我们将其Frank Number $ f（g）$定义为最低数字$ k $，以使$ k $ g $的属性存在$ k $的方向，而每个边缘至少在这些方向中的一个中都可以将每个边缘变成可删除的弧线。我们有兴趣找到坦率的数字的良好上限。我们证明，每3美元连接的图形$ f（g）\ leq 7 $。另一方面，我们证明了Petersen Graph获得了坦率的$ 3 $。此外，我们证明了更多受限制的图形类别的上限，并与Berge-Fulkerson猜想建立了联系。我们还表明，确定给定子集的所有边缘是否可以在一个方向上删除是NP完整的。
We attempt to generalize a theorem of Nash-Williams stating that a graph has a $k$-arc-connected orientation if and only if it is $2k$-edge-connected. In a strongly connected digraph we call an arc {\it deletable} if its deletion leaves a strongly connected digraph. Given a $3$-edge-connected graph $G$, we define its Frank number $f(G)$ to be the minimum number $k$ such that there exist $k$ orientations of $G$ with the property that every edge becomes a deletable arc in at least one of these orientations. We are interested in finding a good upper bound for the Frank number. We prove that $f(G)\leq 7$ for every $3$-edge-connected graph. On the other hand, we show that a Frank number of $3$ is attained by the Petersen graph. Further, we prove better upper bounds for more restricted classes of graphs and establish a connection to the Berge-Fulkerson conjecture. We also show that deciding whether all edges of a given subset can become deletable in one orientation is NP-complete.
